Submission #65841

#	Time	Username	Problem	Language	Result	Execution time	Memory
65841		gs18115	먼 별 (KOI16_dist)	C++14	100 / 100	422 ms	17184 KiB

dist

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL MAXN=3e4+10;
const LL INF=1e18;
void swap(LL&a,LL&b)
{
    a=a^b;
    b=a^b;
    a=a^b;
    return;
}
struct vect
{
    LL x,y;
    vect()
    {
        x=y=0;
    }
    vect(LL a,LL b)
    {
        x=a;
        y=b;
    }
    LL operator * (vect v)
    {
        return x*v.y-y*v.x;
    }
}V[MAXN];
struct point
{
    LL x,y;
    LL x1,y1;
    point()
    {
        x=y=x1=y1=0;
    }
    point(LL a,LL b)
    {
        x=a;
        y=b;
        x1=y1=1;
    }
    point(LL a,LL b,LL c,LL d)
    {
        x=a;
        y=b;
        x1=c;
        y1=d;
    }
    bool operator < (point p)
    {
        return x1*p.y1==y1*p.x1?(y==p.y?x<p.x:y<p.y):y1*p.x1<x1*p.y1;
    }
}P[MAXN];
bool operator > (point a,point b)
{
    return b<a;
}
LL ccw(point p,point x,point y)
{
    return (x.x-p.x)*(y.y-p.y)-(x.y-p.y)*(y.x-p.x);
}
LL DISQ(point p,point q)
{
    return (p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y);
}
LL N;
LL S[MAXN],csz;
LL xx[MAXN],yy[MAXN],dx[MAXN],dy[MAXN];
LL solv(LL T)
{
    LL i,j,maxi=0;
    for(i=0;i<N;i++)
    {
        P[i].x=xx[i]+dx[i]*T;
        P[i].y=yy[i]+dy[i]*T;
        P[i].x1=P[i].y1=1;
        if(P[maxi]>P[i])
            maxi=i;
    }
    if(maxi!=0)
        swap(P[0],P[maxi]);
    for(i=0;i<N;i++)
    {
        P[i].x1=P[i].x-P[0].x;
        P[i].y1=P[i].y-P[0].y;
    }
    sort(P+1,P+N);
    S[0]=0;
    S[1]=1;
    csz=2;
    for(i=2;i<N;i++)
    {
        while(csz>1&&ccw(P[S[csz-2]],P[S[csz-1]],P[i])<=0)
            csz--;
        S[csz++]=i;
    }
    V[csz-1]=vect(P[S[0]].x-P[S[csz-1]].x,P[S[0]].y-P[S[csz-1]].y);
    for(i=1;i<csz;i++)
        V[i-1]=vect(P[S[i]].x-P[S[i-1]].x,P[S[i]].y-P[S[i-1]].y);
    maxi=0;
    for(i=0,j=1;i<N;i++)
    {
        while(V[i]*V[j]>0)
        {
            j++;
            if(j==csz)
                j=0;
        }
        maxi=max(maxi,DISQ(P[S[i]],P[S[j]]));
        maxi=max(maxi,DISQ(P[S[i]],P[S[j==csz-1?0:j+1]]));
    }
    return maxi;
}
vect TS(LL T)
{
    LL s=0,e=T;
    LL mid1,mid2;
    while(s<e-3)
    {
        mid1=(s*2+e)/3;
        mid2=(s+e*2)/3;
        if(solv(mid1)>solv(mid2))
            s=mid1;
        else
            e=mid2;
    }
    mid2=INF;
    for(LL i=s;i<=e;i++)
    {
        mid1=solv(i);
        if(mid2>mid1)
        {
            s=i;
            mid2=mid1;
        }
    }
    return vect(s,mid2);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    LL T,i;
    cin>>N>>T;
    for(i=0;i<N;i++)
        cin>>xx[i]>>yy[i]>>dx[i]>>dy[i];
    vect ans=TS(T);
    cout<<ans.x<<'\n'<<ans.y;
    return 0;
}

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