oj.uz

답안 #44817

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
44817 2018-04-07T07:19:53 Z leehosu01 먼 별 (KOI16_dist) C++17
2 / 100
 122 ms 2132 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;
    do{
        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]));
        }
        if(slop(S[*I],S[*It])<slop(S[*J],S[*Jt]))++I;
        else ++J;
    }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[*It].Ds(S[*J]));
        MX=max(MX,S[*I].Ds(S[*Jt]));
        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:107:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         m=l+r>>1;
           ~^~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 440 KB Output is correct
6 Correct 2 ms 440 KB Output is correct
7 Correct 2 ms 440 KB Output is correct
8 Correct 2 ms 540 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 592 KB Output is correct

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 440 KB Output is correct
6 Correct 2 ms 440 KB Output is correct
7 Correct 2 ms 440 KB Output is correct
8 Correct 2 ms 540 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 16 ms 592 KB Output is correct
12 Correct 17 ms 592 KB Output is correct
13 Correct 16 ms 740 KB Output is correct
14 Correct 17 ms 740 KB Output is correct
15 Correct 10 ms 740 KB Output is correct
16 Correct 13 ms 740 KB Output is correct
17 Correct 16 ms 740 KB Output is correct
18 Correct 10 ms 740 KB Output is correct
19 Correct 15 ms 740 KB Output is correct
20 Incorrect 18 ms 740 KB Output isn't correct

Subtask #3
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 1096 KB Output is correct
2 Correct 120 ms 1096 KB Output is correct
3 Correct 116 ms 1096 KB Output is correct
4 Correct 95 ms 2020 KB Output is correct
5 Correct 85 ms 2020 KB Output is correct
6 Correct 118 ms 2132 KB Output is correct
7 Incorrect 110 ms 2132 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 440 KB Output is correct
6 Correct 2 ms 440 KB Output is correct
7 Correct 2 ms 440 KB Output is correct
8 Correct 2 ms 540 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 16 ms 592 KB Output is correct
12 Correct 17 ms 592 KB Output is correct
13 Correct 16 ms 740 KB Output is correct
14 Correct 17 ms 740 KB Output is correct
15 Correct 10 ms 740 KB Output is correct
16 Correct 13 ms 740 KB Output is correct
17 Correct 16 ms 740 KB Output is correct
18 Correct 10 ms 740 KB Output is correct
19 Correct 15 ms 740 KB Output is correct
20 Incorrect 18 ms 740 KB Output isn't correct