| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 113210 | knon0501 | 먼 별 (KOI16_dist) | C++14 | 0 ms | 0 KiB |
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 <bits/stdc++.h>
using namespace std;
int n,t;
#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];
ll ans=8e18+2e17;
int tt;
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;
for(mid=lef ; mid<=rig ; mid++{
mid=(lef+rig)/2;
ll w=process(mid);
if(w<ans){
ans=w;
tt=mid;
}
}
cout<<tt<<endl<<ans;
return 0;
}