답안 #65841 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65841	2018-08-09T02:06:18 Z	gs18115	먼 별 (KOI16_dist)	C++14	100 / 100	422 ms	17184 KB

dist

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL MAXN=3e4+10;
const LL INF=1e18;
void swap(LL&a,LL&b)
{
    a=a^b;
    b=a^b;
    a=a^b;
    return;
}
struct vect
{
    LL x,y;
    vect()
    {
        x=y=0;
    }
    vect(LL a,LL b)
    {
        x=a;
        y=b;
    }
    LL operator * (vect v)
    {
        return x*v.y-y*v.x;
    }
}V[MAXN];
struct point
{
    LL x,y;
    LL x1,y1;
    point()
    {
        x=y=x1=y1=0;
    }
    point(LL a,LL b)
    {
        x=a;
        y=b;
        x1=y1=1;
    }
    point(LL a,LL b,LL c,LL d)
    {
        x=a;
        y=b;
        x1=c;
        y1=d;
    }
    bool operator < (point p)
    {
        return x1*p.y1==y1*p.x1?(y==p.y?x<p.x:y<p.y):y1*p.x1<x1*p.y1;
    }
}P[MAXN];
bool operator > (point a,point b)
{
    return b<a;
}
LL ccw(point p,point x,point y)
{
    return (x.x-p.x)*(y.y-p.y)-(x.y-p.y)*(y.x-p.x);
}
LL DISQ(point p,point q)
{
    return (p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y);
}
LL N;
LL S[MAXN],csz;
LL xx[MAXN],yy[MAXN],dx[MAXN],dy[MAXN];
LL solv(LL T)
{
    LL i,j,maxi=0;
    for(i=0;i<N;i++)
    {
        P[i].x=xx[i]+dx[i]*T;
        P[i].y=yy[i]+dy[i]*T;
        P[i].x1=P[i].y1=1;
        if(P[maxi]>P[i])
            maxi=i;
    }
    if(maxi!=0)
        swap(P[0],P[maxi]);
    for(i=0;i<N;i++)
    {
        P[i].x1=P[i].x-P[0].x;
        P[i].y1=P[i].y-P[0].y;
    }
    sort(P+1,P+N);
    S[0]=0;
    S[1]=1;
    csz=2;
    for(i=2;i<N;i++)
    {
        while(csz>1&&ccw(P[S[csz-2]],P[S[csz-1]],P[i])<=0)
            csz--;
        S[csz++]=i;
    }
    V[csz-1]=vect(P[S[0]].x-P[S[csz-1]].x,P[S[0]].y-P[S[csz-1]].y);
    for(i=1;i<csz;i++)
        V[i-1]=vect(P[S[i]].x-P[S[i-1]].x,P[S[i]].y-P[S[i-1]].y);
    maxi=0;
    for(i=0,j=1;i<N;i++)
    {
        while(V[i]*V[j]>0)
        {
            j++;
            if(j==csz)
                j=0;
        }
        maxi=max(maxi,DISQ(P[S[i]],P[S[j]]));
        maxi=max(maxi,DISQ(P[S[i]],P[S[j==csz-1?0:j+1]]));
    }
    return maxi;
}
vect TS(LL T)
{
    LL s=0,e=T;
    LL mid1,mid2;
    while(s<e-3)
    {
        mid1=(s*2+e)/3;
        mid2=(s+e*2)/3;
        if(solv(mid1)>solv(mid2))
            s=mid1;
        else
            e=mid2;
    }
    mid2=INF;
    for(LL i=s;i<=e;i++)
    {
        mid1=solv(i);
        if(mid2>mid1)
        {
            s=i;
            mid2=mid1;
        }
    }
    return vect(s,mid2);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    LL T,i;
    cin>>N>>T;
    for(i=0;i<N;i++)
        cin>>xx[i]>>yy[i]>>dx[i]>>dy[i];
    vect ans=TS(T);
    cout<<ans.x<<'\n'<<ans.y;
    return 0;
}

Subtask #1
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1784 KB	Output is correct
2	Correct	4 ms	1896 KB	Output is correct
3	Correct	4 ms	2016 KB	Output is correct
4	Correct	3 ms	2016 KB	Output is correct
5	Correct	4 ms	2016 KB	Output is correct
6	Correct	4 ms	2108 KB	Output is correct
7	Correct	3 ms	2108 KB	Output is correct
8	Correct	4 ms	2108 KB	Output is correct
9	Correct	4 ms	2136 KB	Output is correct
10	Correct	3 ms	2136 KB	Output is correct

Subtask #2
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1784 KB	Output is correct
2	Correct	4 ms	1896 KB	Output is correct
3	Correct	4 ms	2016 KB	Output is correct
4	Correct	3 ms	2016 KB	Output is correct
5	Correct	4 ms	2016 KB	Output is correct
6	Correct	4 ms	2108 KB	Output is correct
7	Correct	3 ms	2108 KB	Output is correct
8	Correct	4 ms	2108 KB	Output is correct
9	Correct	4 ms	2136 KB	Output is correct
10	Correct	3 ms	2136 KB	Output is correct
11	Correct	16 ms	2236 KB	Output is correct
12	Correct	14 ms	2508 KB	Output is correct
13	Correct	11 ms	2508 KB	Output is correct
14	Correct	12 ms	2508 KB	Output is correct
15	Correct	14 ms	2536 KB	Output is correct
16	Correct	8 ms	2536 KB	Output is correct
17	Correct	11 ms	2536 KB	Output is correct
18	Correct	9 ms	2592 KB	Output is correct
19	Correct	10 ms	2604 KB	Output is correct
20	Correct	14 ms	2604 KB	Output is correct

Subtask #3
39.0 / 39.0

#	결과	실행 시간	메모리	Grader output
1	Correct	90 ms	4240 KB	Output is correct
2	Correct	82 ms	4772 KB	Output is correct
3	Correct	86 ms	5356 KB	Output is correct
4	Correct	66 ms	6200 KB	Output is correct
5	Correct	84 ms	6640 KB	Output is correct
6	Correct	75 ms	7304 KB	Output is correct
7	Correct	62 ms	7644 KB	Output is correct
8	Correct	51 ms	8100 KB	Output is correct
9	Correct	80 ms	8912 KB	Output is correct
10	Correct	94 ms	9316 KB	Output is correct

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1784 KB	Output is correct
2	Correct	4 ms	1896 KB	Output is correct
3	Correct	4 ms	2016 KB	Output is correct
4	Correct	3 ms	2016 KB	Output is correct
5	Correct	4 ms	2016 KB	Output is correct
6	Correct	4 ms	2108 KB	Output is correct
7	Correct	3 ms	2108 KB	Output is correct
8	Correct	4 ms	2108 KB	Output is correct
9	Correct	4 ms	2136 KB	Output is correct
10	Correct	3 ms	2136 KB	Output is correct
11	Correct	16 ms	2236 KB	Output is correct
12	Correct	14 ms	2508 KB	Output is correct
13	Correct	11 ms	2508 KB	Output is correct
14	Correct	12 ms	2508 KB	Output is correct
15	Correct	14 ms	2536 KB	Output is correct
16	Correct	8 ms	2536 KB	Output is correct
17	Correct	11 ms	2536 KB	Output is correct
18	Correct	9 ms	2592 KB	Output is correct
19	Correct	10 ms	2604 KB	Output is correct
20	Correct	14 ms	2604 KB	Output is correct
21	Correct	90 ms	4240 KB	Output is correct
22	Correct	82 ms	4772 KB	Output is correct
23	Correct	86 ms	5356 KB	Output is correct
24	Correct	66 ms	6200 KB	Output is correct
25	Correct	84 ms	6640 KB	Output is correct
26	Correct	75 ms	7304 KB	Output is correct
27	Correct	62 ms	7644 KB	Output is correct
28	Correct	51 ms	8100 KB	Output is correct
29	Correct	80 ms	8912 KB	Output is correct
30	Correct	94 ms	9316 KB	Output is correct
31	Correct	385 ms	10012 KB	Output is correct
32	Correct	409 ms	10588 KB	Output is correct
33	Correct	351 ms	10996 KB	Output is correct
34	Correct	344 ms	11732 KB	Output is correct
35	Correct	357 ms	12312 KB	Output is correct
36	Correct	422 ms	13240 KB	Output is correct
37	Correct	323 ms	13596 KB	Output is correct
38	Correct	197 ms	14348 KB	Output is correct
39	Correct	255 ms	14932 KB	Output is correct
40	Correct	369 ms	15624 KB	Output is correct
41	Correct	320 ms	16576 KB	Output is correct
42	Correct	340 ms	17184 KB	Output is correct

답안 #65841

Compilation message

Subtask #1 2.0 / 2.0

Subtask #2 40.0 / 40.0

Subtask #3 39.0 / 39.0

Subtask #4 19.0 / 19.0

Subtask #1
2.0 / 2.0

Subtask #2
40.0 / 40.0

Subtask #3
39.0 / 39.0

Subtask #4
19.0 / 19.0