Submission #113218

#	Time	Username	Problem	Language	Result	Execution time	Memory
113218		knon0501	먼 별 (KOI16_dist)	C++14	100 / 100	475 ms	3044 KiB

dist

#include <bits/stdc++.h>
using namespace std;
int n,t;
#define mp make_pair
#define x first
#define y second
typedef long long ll;
typedef pair<ll,ll> pp;
pp a[300005];
pp v[300005];
pp s[300005];
pp b[300005];
pair<ll,int> ans={8e18+2e17,1e9};

long double f(pp q,pp w,pp e){
    ll aa=q.y-w.y;
    ll bb=w.x-q.x;
    ll cc=q.x*w.y-q.y*w.x;
    return (long double)(aa*e.x+bb*e.y+cc)/sqrt((long double)(aa*aa+bb*bb));
}
ll ccw(pp q,pp w,pp e){
    return (w.x-q.x)*(e.y-w.y)-(w.y-q.y)*(e.x-w.x);
}
ll dist(pp q,pp w){
    return (w.x-q.x)*(w.x-q.x)+(w.y-q.y)*(w.y-q.y);
}
bool comp(pp q,pp w){
    ll k=ccw(b[1],q,w);
    return k ? k>0 : dist(b[1],q)<dist(b[1],w);
}
ll process(ll ti){
    if(ti<0 || ti>t)return 1e18;
    int i,j;
    ll ret=0;
    for(i=1 ; i<=n ; i++)b[i]={a[i].x+ti*v[i].x,a[i].y+ti*v[i].y};
    sort(b+1,b+n+1);
    sort(b+2,b+n+1,comp);
    ret=dist(b[1],b[n]);
    int to=2;
    s[1]=b[1];
    s[2]=b[2];
    b[n+1]=b[1];
    for(i=3 ; i<=n+1 ; i++){
        while(to>=2 && ccw(s[to-1],s[to],b[i])<=0)to--;
        s[++to]=b[i];
    }
    to--;
    if(to<3)return ret;
   /// cout<<to<<" "<<ti<<endl;
    j=2;
    for(i=1 ; i<=to ; i++){
        int ii=i%to+1;
        if(j>to)j=1;
        while(f(s[i],s[ii],s[j%to+1])>f(s[i],s[ii],s[j]) ){
            ret=max({ret,dist(s[i],s[j]),dist(s[ii],s[j])});
            j++;
            if(j>to)j=1;
        }
        ret=max({ret,dist(s[i],s[j]),dist(s[ii],s[j])});
    }
   /// cout<<ret<<endl;
    return ret;
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    cin>>n>>t;

    int i;
    for(i=1 ; i<=n ; i++)cin>>a[i].x>>a[i].y>>v[i].x>>v[i].y;

    int lef=0;
    int rig=t;

    while(rig>=lef){
        int mid=(lef+rig)/2;
        ll q=process(mid-1);
        ll w=process(mid);
        ll e=process(mid+1);
        if(mp(q,mid-1)<ans){
            ans={q,mid-1};
        }
        if(mp(w,mid)<ans){
            ans={w,mid};
        }
        if(mp(e,mid+1)<ans){
            ans={e,mid+1};
        }
        if(q>w && w>e)lef=mid+1;
        else rig=mid-1;
    }
    cout<<ans.second<<endl<<ans.first;

    return 0;
}

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