이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long ll;
struct star{
ll xx,yy,dx,dy;
}input[30010];
ll n,maxday,top;
struct nowstar{
ll x, y;
}now[30010],st[30010];
ll cross(ll a, ll b, ll c, ll d)
{
return a*d-b*c;
}
bool ccmp(nowstar A, nowstar B)
{
if(A.x==B.x) return A.y<B.y;
return A.x<B.x;
}
bool rcmp(nowstar A, nowstar B)
{
return cross(A.x-now[1].x,A.y-now[1].y,B.x-now[1].x,B.y-now[1].y)>=0;
}
ll f(ll x){return ((x-1)%top)+1;}
ll dist(nowstar A, nowstar B)
{
return ((B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y));
}
ll maxdis(ll day)
{
ll i,j;
top=0;
for(i=1;i<=n;i++)
{
now[i].x=input[i].xx+input[i].dx*(ll)day;
now[i].y=input[i].yy+input[i].dy*(ll)day;
}
sort(now+1,now+n+1,ccmp);
sort(now+2,now+n+1,rcmp);
st[++top]=now[1];
st[++top]=now[2];
for(i=3;i<=n;i++)
{
while(cross(st[top].x-st[top-1].x,st[top].y-st[top-1].y,now[i].x-st[top].x,now[i].y-st[top].y)<=0&&top>=2) top--;
st[++top]=now[i];
}
ll ret=0;
if(top==1) return 0;
if(top==2) return dist(st[1],st[2]);
for(i=1,j=2;i<=top;i++)
{
while(cross(st[f(i+1)].x-st[f(i)].x,st[f(i+1)].y-st[f(i)].y,st[f(j+1)].x-st[f(j)].x,st[f(j+1)].y-st[f(j)].y)>=0)j++;
ret=max(ret,dist(st[f(i)],st[f(j)]));
ret=max(ret,dist(st[f(i)],st[f(j+1)]));
}
return ret;
}
int main()
{
ll i;
scanf("%lld %lld",&n, &maxday);
for(i=1;i<=n;i++)
{
scanf("%lld %lld %lld %lld", &input[i].xx, &input[i].yy, &input[i].dx, &input[i].dy);
}
ll ci=50;
ll l=0, r=maxday, x1, x2;
while(ci--&&l+1<r)
{
x1=(2*l+r)/3;
x2=(2*r+l)/3;
if(maxdis(x1)>maxdis(x2)) l=x1;
else r=x2;
}
ll ans1=maxdis(l),ans2=l;
for(i=l+1;i<=r;i++)
{
if(maxdis(i)<ans1)
{
ans1=maxdis(i);
ans2=i;
}
}
printf("%lld\n%lld", ans2,ans1);
}
컴파일 시 표준 에러 (stderr) 메시지
dist.cpp: In function 'int main()':
dist.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld",&n, &maxday);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
dist.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld %lld", &input[i].xx, &input[i].yy, &input[i].dx, &input[i].dy);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |