This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <algorithm>
using namespace std;
/*
input에서 별들의 초기 위치는 (xx,yy)고 속도벡터가 (dx,dy)
nowstar 구조체는 날짜에 맞는 별들의 위치만 저장해주는 구조체이다.
st배열은 컨벡스홀에 쓰이는 스택 배열이다.
*/
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) //벡터곱을 해주는 함수 양수면 ccw, 음수면 cw 0이면 직선
{
return (ll)((ll)a*d-(ll)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%top;}
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) //day번째 날에 가장 먼 두 점 사이 거리를 반환해주는 함수
{
ll i,j,ret=0;
top=0;
//날짜에 맞게 별들의 위치를 조정해줌
for(i=1;i<=n;i++)
{
now[i].x=input[i].xx+input[i].dx*day;
now[i].y=input[i].yy+input[i].dy*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++)
{
if(now[i].x==now[i-1].x&&now[i].y==now[i-1].y) continue;
while(top>=2&&cross(st[top-1].x-st[top-2].x,st[top-1].y-st[top-2].y,now[i].x-st[top-1].x,now[i].y-st[top-1].y)<=0) top--;
st[top++]=now[i];
}
//가장 먼 두 점 사이 거리를 구하는 부분
if(top==2)
{
return dist(st[0],st[1]);
}
for(i=0,j=0;i<top;i++)
{
if(i==j) j=(j+1)%top;
int ni=(i+1)%top,nj=(j+1)%top;
while(cross(st[ni].x-st[f(i)].x,st[ni].y-st[i].y,st[nj].x-st[j].x,st[nj].y-st[j].y)>0){nj=(nj+1)%top,j=(j+1)%top;}
ret=max(ret,dist(st[i],st[j]));
}
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 l=0, r=maxday, x1, x2,ci=50;
//3분탐색으로 최소점을 찾음
while(ci--&&l+1<r)
{
x1=((ll)2*l+r)/3;
x2=((ll)2*r+l)/3;
if(maxdis(x1)>maxdis(x2)) l=x1;
else r=x2;
}
//확실하게 하기 위해 l과 r범위내에서 다시 최소를 찾음
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);
}
Compilation message (stderr)
dist.cpp: In function 'int main()':
dist.cpp:73: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:76: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... |