oj.uz

Submission #44809

# Submission time Handle Problem Language Result Execution time Memory
44809 2018-04-07T06:07:20 Z leehosu01 None (KOI16_dist) C++17
2 / 100
 127 ms 6532 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define F(X) (X<0?-1:X>0)
ll T,MT,N,tms,bst=1ll<<62ll;
struct A{
int x,y,dx,dy;void SC(){cin>>x>>y>>dx>>dy;}
ll lcx(){return T*dx+x;}
ll lcy(){return T*dy+y;}
bool operator<(const A&X)const{return T*dx+x==T*X.dx+X.x?T*dy+y>T*X.dy+X.y:T*dx+x<T*X.dx+X.x;}
ll Ds(A&X){return (lcx()-X.lcx())*(lcx()-X.lcx())+(lcy()-X.lcy())*(lcy()-X.lcy());}
}S[30000];
int cp(ll*X,ll*Y)
{
    ll T=0;
    for(int i=0;i<3;i++)
        T+=X[i]*Y[i+1]-X[i+1]*Y[i];
    return F(T);
}
int ccw(A&x0,A&x1,A&x2)
{
    A XA[4]={x0,x1,x2,x0};
    ll XX[4],YY[4];
    for(int i=0;i<4;i++)
    {
        XX[i]=XA[i].lcx();
        YY[i]=XA[i].lcy();
    }
    return cp(XX,YY);
}
#define nxt(X,Xp) Xp=X;if(++Xp==cov.end())Xp=cov.begin()
inline ld slop(A&d1,A&d2)
{
    return ((ld)d1.lcx()-d2.lcx())/((ld)d1.lcy()-d2.lcy());
}
bool used[30001];
ll pro(int Ts)
{
 
    list<int>::iterator s1,s2;
    list<int>cov;
    T=Ts;
    sort(S,S+N);
    int K=1;
    memset(used,0,sizeof(used));
    for(int i=0;i>=0;i+=K)
    {
        if(i==N){K=-1,s1=cov.begin(),s2=--cov.end();continue;}
        if(i!=0&&used[i])continue;
        while(cov.size()>=2&&ccw(S[*(--(--cov.end()))],S[cov.back()],S[i])==-1){used[cov.back()]=0;cov.pop_back();}
        used[i]=1;cov.push_back(i);
    }//시작정점은 2번들어간다.
 
    ll MX=0;
    list<int>::iterator I=s1,It,J=s2,Jt;
    bool mdgd=0;
    do{
        if(mdgd)
        {
            if(slop(S[*I],S[*It])<slop(S[*J],S[*Jt]))++I;
            else ++J;
        }
        It=I;++It;
        Jt=J;++Jt;
        if(Jt==cov.end())break;
        MX=max(MX,S[*I].Ds(S[*J]));
        MX=max(MX,S[*I].Ds(S[*Jt]));
        MX=max(MX,S[*It].Ds(S[*J]));
        MX=max(MX,S[*It].Ds(S[*Jt]));
        mdgd=1;
    }while(I!=s2&&J!=cov.end());
    if(MX<bst)bst=MX,tms=Ts;
    else if(MX==bst&&tms>Ts)tms=Ts;
    return MX;
}
 
int main()
{
    int i;
    cin>>N>>MT;
    for(i=0;i<N;i++)S[i].SC();
    ll l=0,r=MT,m,PS[3],minl,minI;
    while(l<r)
    {
        m=l+r>>1;
        minl=1ll<<62ll;
        minI=-1;
        for(i=-1;i<2;i++)
        {
            if(m+i>=0&&m+i<=MT)
            {
                PS[i+1]=pro(m+i);
                if(PS[i+1]<minl)
                {
                    minl=PS[i+1];
                    minI=i;
                }
            }
        }
        if(minI==-1)r=m-1;
        else if(minI==0)r=m;
        else l=m+1;
    }
    cout<<tms<<'\n'<<bst;
 
}

Compilation message

dist.cpp: In function 'int main()':
dist.cpp:87:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         m=l+r>>1;
           ~^~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 396 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 2 ms 480 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 2 ms 580 KB Output is correct
8 Correct 2 ms 584 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 644 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 396 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 2 ms 480 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 2 ms 580 KB Output is correct
8 Correct 2 ms 584 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 644 KB Output is correct
11 Incorrect 18 ms 648 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 1224 KB Output is correct
2 Correct 113 ms 1696 KB Output is correct
3 Correct 123 ms 2244 KB Output is correct
4 Correct 107 ms 3940 KB Output is correct
5 Correct 88 ms 4480 KB Output is correct
6 Correct 91 ms 5100 KB Output is correct
7 Correct 102 ms 5476 KB Output is correct
8 Correct 68 ms 5796 KB Output is correct
9 Incorrect 127 ms 6532 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 396 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 2 ms 480 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 2 ms 580 KB Output is correct
8 Correct 2 ms 584 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 644 KB Output is correct
11 Incorrect 18 ms 648 KB Output isn't correct
12 Halted 0 ms 0 KB -