oj.uz

Submission #113214

# Submission time Handle Problem Language Result Execution time Memory
113214 2019-05-24T10:47:25 Z knon0501 None (KOI16_dist) C++14
41 / 100
 2000 ms 3080 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(int mid=lef ; mid<=rig ; mid++){
        ll w=process(mid);
        if(w<ans){
            ans=w;
            tt=mid;
        }
 
    }
    cout<<tt<<endl<<ans;
 
    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 504 KB Output is correct
2 Correct 265 ms 384 KB Output is correct
3 Correct 259 ms 384 KB Output is correct
4 Correct 263 ms 384 KB Output is correct
5 Correct 262 ms 504 KB Output is correct
6 Correct 273 ms 504 KB Output is correct
7 Correct 273 ms 504 KB Output is correct
8 Correct 299 ms 452 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 270 ms 384 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 504 KB Output is correct
2 Correct 265 ms 384 KB Output is correct
3 Correct 259 ms 384 KB Output is correct
4 Correct 263 ms 384 KB Output is correct
5 Correct 262 ms 504 KB Output is correct
6 Correct 273 ms 504 KB Output is correct
7 Correct 273 ms 504 KB Output is correct
8 Correct 299 ms 452 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 270 ms 384 KB Output is correct
11 Execution timed out 2054 ms 384 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 2176 KB Output is correct
2 Correct 143 ms 2356 KB Output is correct
3 Correct 135 ms 2360 KB Output is correct
4 Correct 185 ms 2908 KB Output is correct
5 Correct 103 ms 2564 KB Output is correct
6 Correct 153 ms 2900 KB Output is correct
7 Correct 93 ms 2304 KB Output is correct
8 Correct 59 ms 2176 KB Output is correct
9 Correct 140 ms 3080 KB Output is correct
10 Correct 154 ms 2620 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 504 KB Output is correct
2 Correct 265 ms 384 KB Output is correct
3 Correct 259 ms 384 KB Output is correct
4 Correct 263 ms 384 KB Output is correct
5 Correct 262 ms 504 KB Output is correct
6 Correct 273 ms 504 KB Output is correct
7 Correct 273 ms 504 KB Output is correct
8 Correct 299 ms 452 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 270 ms 384 KB Output is correct
11 Execution timed out 2054 ms 384 KB Time limit exceeded
12 Halted 0 ms 0 KB -