제출 #57752

#제출 시각아이디문제언어결과실행 시간메모리
57752red1108먼 별 (KOI16_dist)C++17
100 / 100
1117 ms12128 KiB
#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)
{
    if(cross(A.x-now[1].x,A.y-now[1].y,B.x-now[1].x,B.y-now[1].y)==0)
    {
        if (A.x==B.x) return A.y<B.y;
        return A.x<B.x;
    }
    return cross(A.x-now[1].x,A.y-now[1].y,B.x-now[1].x,B.y-now[1].y)>0;
}
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,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];
    }
    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[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;
    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;
    }
    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:58: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:61: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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...