Submission #57754

#	Time	Username	Problem	Language	Result	Execution time	Memory
57754		gs18081	먼 별 (KOI16_dist)	C++11	2 / 100	229 ms	2124 KiB

dist

/*
 #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);
 }
 */
#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pi;

struct star{
    ll x,y,dx,dy;
};
int N,T;
star stars[40000];



ll myabs(ll num){
    return num>0?num:-num;
}
ll delta(pi a,pi b,pi c){
    /*return a.first*b.second - a.second * b.first
     +b.first * c.second - b.second * c.first
     +c.first * a.second - c.second * a.first;
     */
    return (b.first-a.first)*(c.second-a.second) - (b.second-a.second)*(c.first-a.first);
}
ll dist(pi a,pi b){
    return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
ll absdist(pi a,pi b){
    return myabs(a.first-b.first)+myabs(a.second-b.second);
}
vector<pi> dots;
vector<pi> hull;
ll maxdist(int day){
    dots.clear();
    for(int i=0;i<N;i++){
        dots.push_back(pi(stars[i].x+day*stars[i].dx,stars[i].y+stars[i].dy*day));
    }
    
    sort(dots.begin(),dots.end(),[&](pi a,pi b){
        return a.second==b.second?a.first<b.first:a.second<b.second;
    });
    dots.erase(unique(dots.begin(),dots.end()),dots.end());
    sort(dots.begin()+1,dots.end(),[&](pi a,pi b){
        if(delta(dots[0],a,b)==0){
            if(a.first==b.first) return a.second<b.second;
            return a.first<b.first;
        }
        return delta(dots[0],a,b)<0;
        //return delta(dots[0],a,b)==0?absdist(dots[0],a)<absdist(dots[0],b) : delta(dots[0],a,b)>0;
    });
    hull.clear();
    hull.push_back(dots[0]);
    for(int i=1;i<dots.size();i++){
        while(hull.size()>=2&&delta(hull[hull.size()-2],hull.back(),dots[i])<=0) hull.pop_back();
        hull.push_back(dots[i]);
    }
    ll ret=0;
    int j=1%hull.size();
    for(int i=0;i<hull.size();i++){
        int ni=(i+1)%hull.size();
        for(;;){
            int nj=(j+1)%hull.size();
            if(delta(pi(0,0),pi(hull[ni].first-hull[i].first,hull[ni].second-hull[i].second),pi(hull[nj].first-hull[j].first,hull[nj].second-hull[j].second))<=0)
                break;
            j=nj;
        }
        ret=max(ret,dist(hull[i],hull[j]));
    }
    return ret;
}
int main(){
    scanf("%d %d",&N,&T);
    for(int i=0;i<N;i++){
        scanf("%lld %lld %lld %lld",&stars[i].x,&stars[i].y,&stars[i].dx,&stars[i].dy);
    }
    int s=0;
    int e=T;
    ll ans=maxdist(0);
    int day=0,x1,x2;
    while(s+5<e){
        x1=((ll)2*s+e)/3;
        x2=((ll)2*e+s)/3;
        if(maxdist(x1)>maxdist(x2)) s=x1;
        else e=x2;
    }
    if(e<s) swap(s,e);
    //*/
    if(T<=20){
        s=0;
        e=T;
    }
    //*/
    ans=maxdist(s);
    day=s;
    for(int i=s+1;i<=e;i++){
        if(ans>maxdist(i)){
            day=i;
            ans=maxdist(i);
        }
    }
    printf("%d\n%lld\n",day,ans);
    return 0;
}

Compilation message (stderr)

dist.cpp: In function 'll maxdist(int)':
dist.cpp:136:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<dots.size();i++){
                 ~^~~~~~~~~~~~
dist.cpp:142:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<hull.size();i++){
                 ~^~~~~~~~~~~~
dist.cpp: In function 'int main()':
dist.cpp:155:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&T);
     ~~~~~^~~~~~~~~~~~~~~
dist.cpp:157:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld %lld",&stars[i].x,&stars[i].y,&stars[i].dx,&stars[i].dy);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 0 / 40
• Subtask 3: 0 / 39
• Subtask 4: 0 / 19