oj.uz

Submission #57609

# Submission time Handle Problem Language Result Execution time Memory
57609 2018-07-15T12:15:28 Z red1108 None (KOI16_dist) C++17
2 / 100
 954 ms 5212 KB 
#include <stdio.h>
#include <algorithm>
using namespace std;
/*
input에서 별들의 초기 위치는 (xx,yy)고 속도벡터가 (dx,dy)
nowstar 구조체는 날짜에 맞는 별들의 위치만 저장해주는 구조체이다.
st배열은 컨벡스홀에 쓰이는 스택 배열이다.
*/
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) //벡터곱을 해주는 함수 양수면 ccw, 음수면 cw 0이면 직선
{
    return (ll)((ll)a*d-(ll)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) //각도순으로 정렬해주는 함수
{
    return cross(A.x-now[1].x,A.y-now[1].y,B.x-now[1].x,B.y-now[1].y)>0;
}
ll f(ll x){return x%top;}
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) //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];
    }
    //가장 먼 두 점 사이 거리를 구하는 부분
    if(top==2)
    {
        return dist(st[0],st[1]);
    }
    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[f(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;
    //3분탐색으로 최소점을 찾음
    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;
    }
    //확실하게 하기 위해 l과 r범위내에서 다시 최소를 찾음
    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:73: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:76: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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 2 ms 528 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 2 ms 600 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 2 ms 528 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 27 ms 704 KB Output is correct
12 Correct 26 ms 704 KB Output is correct
13 Correct 20 ms 708 KB Output is correct
14 Correct 23 ms 728 KB Output is correct
15 Incorrect 13 ms 752 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 954 ms 2832 KB Output is correct
2 Correct 829 ms 3372 KB Output is correct
3 Correct 918 ms 3900 KB Output is correct
4 Correct 280 ms 4996 KB Output is correct
5 Incorrect 131 ms 5212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 2 ms 528 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 27 ms 704 KB Output is correct
12 Correct 26 ms 704 KB Output is correct
13 Correct 20 ms 708 KB Output is correct
14 Correct 23 ms 728 KB Output is correct
15 Incorrect 13 ms 752 KB Output isn't correct
16 Halted 0 ms 0 KB -