# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
113210 |
2019-05-24T10:45:19 Z |
knon0501 |
None (KOI16_dist) |
C++14 |
|
0 ms |
0 KB |
#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;
}
Compilation message
dist.cpp: In function 'int main()':
dist.cpp:76:9: error: 'mid' was not declared in this scope
for(mid=lef ; mid<=rig ; mid++{
^~~
dist.cpp:76:35: error: expected ')' before '{' token
for(mid=lef ; mid<=rig ; mid++{
^