답안 #57752 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57752	2018-07-16T01:56:52 Z	red1108	먼 별 (KOI16_dist)	C++17	100 / 100	1117 ms	12128 KB

dist

#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long ll;
struct star{
    ll xx,yy,dx,dy;
}input[30010];
ll n,maxday,top;
struct nowstar{
    ll x, y;
}now[30010],st[30010];
ll cross(ll a, ll b, ll c, ll d){return a*d-b*c;}
bool ccmp(nowstar A, nowstar B)
{
    if(A.x==B.x) return A.y<B.y;
    return A.x<B.x;
}
bool rcmp(nowstar A, nowstar B)
{
    if(cross(A.x-now[1].x,A.y-now[1].y,B.x-now[1].x,B.y-now[1].y)==0)
    {
        if (A.x==B.x) return A.y<B.y;
        return A.x<B.x;
    }
    return cross(A.x-now[1].x,A.y-now[1].y,B.x-now[1].x,B.y-now[1].y)>0;
}
ll dist(nowstar A, nowstar B){return (B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y);}
ll maxdis(ll day)
{
    ll i,j,ret=0,top=0;
    for(i=1;i<=n;i++)
    {
        now[i].x=input[i].xx+input[i].dx*day;
        now[i].y=input[i].yy+input[i].dy*day;
    }
    sort(now+1,now+n+1,ccmp);
    sort(now+2,now+n+1,rcmp);
    st[top++]=now[1];
    st[top++]=now[2];
    for(i=3;i<=n;i++)
    {
        if(now[i].x==now[i-1].x&&now[i].y==now[i-1].y) continue;
        while(top>=2&&cross(st[top-1].x-st[top-2].x,st[top-1].y-st[top-2].y,now[i].x-st[top-1].x,now[i].y-st[top-1].y)<=0) top--;
        st[top++]=now[i];
    }
    for(i=0,j=0;i<top;i++)
    {
        if(i==j) j=(j+1)%top;
        int ni=(i+1)%top,nj=(j+1)%top;
        while(cross(st[ni].x-st[i].x,st[ni].y-st[i].y,st[nj].x-st[j].x,st[nj].y-st[j].y)>0){nj=(nj+1)%top,j=(j+1)%top;}
        ret=max(ret,dist(st[i],st[j]));
    }
    return ret;
}
int main()
{
    ll i;
    scanf("%lld %lld",&n, &maxday);
    for(i=1;i<=n;i++)
    {
        scanf("%lld %lld %lld %lld", &input[i].xx, &input[i].yy, &input[i].dx, &input[i].dy);
    }
    ll l=0, r=maxday, x1, x2,ci=50;
    while(ci--&&l+1<r)
    {
        x1=((ll)2*l+r)/3;
        x2=((ll)2*r+l)/3;
        if(maxdis(x1)>maxdis(x2)) l=x1;
        else r=x2;
    }
    ll ans1=maxdis(l),ans2=l;
    for(i=l+1;i<=r;i++)
    {
        if(maxdis(i)<ans1)
        {
            ans1=maxdis(i);
            ans2=i;
        }
    }
    printf("%lld\n%lld", ans2,ans1);
}

Compilation message

dist.cpp: In function 'int main()':
dist.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld",&n, &maxday);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
dist.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld %lld", &input[i].xx, &input[i].yy, &input[i].dx, &input[i].dy);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

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

Subtask #2
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	540 KB	Output is correct
4	Correct	3 ms	540 KB	Output is correct
5	Correct	3 ms	540 KB	Output is correct
6	Correct	3 ms	540 KB	Output is correct
7	Correct	2 ms	560 KB	Output is correct
8	Correct	2 ms	560 KB	Output is correct
9	Correct	3 ms	560 KB	Output is correct
10	Correct	2 ms	584 KB	Output is correct
11	Correct	24 ms	632 KB	Output is correct
12	Correct	25 ms	660 KB	Output is correct
13	Correct	22 ms	680 KB	Output is correct
14	Correct	28 ms	680 KB	Output is correct
15	Correct	17 ms	724 KB	Output is correct
16	Correct	30 ms	748 KB	Output is correct
17	Correct	19 ms	892 KB	Output is correct
18	Correct	11 ms	892 KB	Output is correct
19	Correct	23 ms	892 KB	Output is correct
20	Correct	21 ms	892 KB	Output is correct

Subtask #3
39.0 / 39.0

#	결과	실행 시간	메모리	Grader output
1	Correct	905 ms	2148 KB	Output is correct
2	Correct	812 ms	2148 KB	Output is correct
3	Correct	877 ms	2276 KB	Output is correct
4	Correct	140 ms	2676 KB	Output is correct
5	Correct	734 ms	2676 KB	Output is correct
6	Correct	1117 ms	2788 KB	Output is correct
7	Correct	486 ms	2788 KB	Output is correct
8	Correct	356 ms	2788 KB	Output is correct
9	Correct	1000 ms	3796 KB	Output is correct
10	Correct	926 ms	3956 KB	Output is correct

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	540 KB	Output is correct
4	Correct	3 ms	540 KB	Output is correct
5	Correct	3 ms	540 KB	Output is correct
6	Correct	3 ms	540 KB	Output is correct
7	Correct	2 ms	560 KB	Output is correct
8	Correct	2 ms	560 KB	Output is correct
9	Correct	3 ms	560 KB	Output is correct
10	Correct	2 ms	584 KB	Output is correct
11	Correct	24 ms	632 KB	Output is correct
12	Correct	25 ms	660 KB	Output is correct
13	Correct	22 ms	680 KB	Output is correct
14	Correct	28 ms	680 KB	Output is correct
15	Correct	17 ms	724 KB	Output is correct
16	Correct	30 ms	748 KB	Output is correct
17	Correct	19 ms	892 KB	Output is correct
18	Correct	11 ms	892 KB	Output is correct
19	Correct	23 ms	892 KB	Output is correct
20	Correct	21 ms	892 KB	Output is correct
21	Correct	905 ms	2148 KB	Output is correct
22	Correct	812 ms	2148 KB	Output is correct
23	Correct	877 ms	2276 KB	Output is correct
24	Correct	140 ms	2676 KB	Output is correct
25	Correct	734 ms	2676 KB	Output is correct
26	Correct	1117 ms	2788 KB	Output is correct
27	Correct	486 ms	2788 KB	Output is correct
28	Correct	356 ms	2788 KB	Output is correct
29	Correct	1000 ms	3796 KB	Output is correct
30	Correct	926 ms	3956 KB	Output is correct
31	Correct	924 ms	4628 KB	Output is correct
32	Correct	887 ms	5164 KB	Output is correct
33	Correct	903 ms	5820 KB	Output is correct
34	Correct	942 ms	6352 KB	Output is correct
35	Correct	711 ms	7140 KB	Output is correct
36	Correct	898 ms	8076 KB	Output is correct
37	Correct	618 ms	8372 KB	Output is correct
38	Correct	396 ms	9056 KB	Output is correct
39	Correct	914 ms	9760 KB	Output is correct
40	Correct	863 ms	10324 KB	Output is correct
41	Correct	712 ms	11468 KB	Output is correct
42	Correct	856 ms	12128 KB	Output is correct

답안 #57752

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