oj.uz

Submission #44821

# Submission time Handle Problem Language Result Execution time Memory
44821 2018-04-07T09:17:17 Z leehosu01 None (KOI16_dist) C++17
2 / 100
 140 ms 2172 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;}
bool operator==(const A&X)const{return T*dx+x==T*X.dx+X.x&&T*dy+y==T*X.dy+X.y;}
ll Ds(A&X){return (lcx()-X.lcx())*(lcx()-X.lcx())+(lcy()-X.lcy())*(lcy()-X.lcy());}
}S[30001];
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);
}
inline ld slop(A&d1,A&d2)
{
    return ((ld)d1.lcy()-d2.lcy())/((ld)d1.lcx()-d2.lcx());
}
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;
        MX=max(MX,S[*I].Ds(S[*J]));
        MX=max(MX,S[*It].Ds(S[*J]));
        if(Jt!=cov.end())
        {
            MX=max(MX,S[*I].Ds(S[*Jt]));
            MX=max(MX,S[*It].Ds(S[*Jt]));
        }
        mdgd=1;
    }while(It!=s2&&Jt!=cov.end());
    
    while(I!=s2&&It!=s2){
        It=I;++It;
        MX=max(MX,S[*I].Ds(S[*J]));
        MX=max(MX,S[*I].Ds(S[*Jt]));
        if(It!=s2)
        {
            MX=max(MX,S[*It].Ds(S[*J]));
            MX=max(MX,S[*It].Ds(S[*Jt]));
        }
        ++I;
    }
    while(J!=cov.end()&&Jt!=cov.end()){
        Jt=J;++Jt;
        MX=max(MX,S[*I].Ds(S[*J]));
        MX=max(MX,S[*It].Ds(S[*J]));
        if(Jt!=cov.end())
        {
            MX=max(MX,S[*I].Ds(S[*Jt]));
            MX=max(MX,S[*It].Ds(S[*Jt]));
        }
        else break;
        ++J;
    }
    if(MX<bst)bst=MX,tms=Ts;
    else if(MX==bst&&tms>Ts)tms=Ts;
    return MX;
}

int main()
{
    int i;

   //freopen("in.txt","r",stdin);
    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:115: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 428 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 552 KB Output is correct
7 Correct 2 ms 684 KB Output is correct
8 Correct 2 ms 684 KB Output is correct
9 Correct 2 ms 740 KB Output is correct
10 Correct 2 ms 740 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 428 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 552 KB Output is correct
7 Correct 2 ms 684 KB Output is correct
8 Correct 2 ms 684 KB Output is correct
9 Correct 2 ms 740 KB Output is correct
10 Correct 2 ms 740 KB Output is correct
11 Correct 24 ms 740 KB Output is correct
12 Correct 18 ms 740 KB Output is correct
13 Correct 17 ms 740 KB Output is correct
14 Correct 17 ms 740 KB Output is correct
15 Correct 10 ms 748 KB Output is correct
16 Correct 13 ms 748 KB Output is correct
17 Correct 26 ms 748 KB Output is correct
18 Correct 10 ms 748 KB Output is correct
19 Correct 12 ms 748 KB Output is correct
20 Incorrect 17 ms 748 KB Output isn't correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 1120 KB Output is correct
2 Correct 114 ms 1120 KB Output is correct
3 Correct 122 ms 1148 KB Output is correct
4 Correct 96 ms 2044 KB Output is correct
5 Correct 89 ms 2044 KB Output is correct
6 Correct 131 ms 2172 KB Output is correct
7 Incorrect 104 ms 2172 KB Output isn't correct
8 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 428 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 552 KB Output is correct
7 Correct 2 ms 684 KB Output is correct
8 Correct 2 ms 684 KB Output is correct
9 Correct 2 ms 740 KB Output is correct
10 Correct 2 ms 740 KB Output is correct
11 Correct 24 ms 740 KB Output is correct
12 Correct 18 ms 740 KB Output is correct
13 Correct 17 ms 740 KB Output is correct
14 Correct 17 ms 740 KB Output is correct
15 Correct 10 ms 748 KB Output is correct
16 Correct 13 ms 748 KB Output is correct
17 Correct 26 ms 748 KB Output is correct
18 Correct 10 ms 748 KB Output is correct
19 Correct 12 ms 748 KB Output is correct
20 Incorrect 17 ms 748 KB Output isn't correct