Submission #23372

#	Time	Username	Problem	Language	Result	Execution time	Memory
23372		TAMREF	먼 별 (KOI16_dist)	C++11	100 / 100	386 ms	3900 KiB

dist

#include <bits/stdc++.h>
#define fst first
#define snd second
using namespace std;
typedef long long ll;
const int MX = 30005;
struct point{
    ll x, y;
    point(ll _x=0,ll _y=0):x(_x),y(_y){}
    ll operator* (point z){return x*z.y-y*z.x;}
    bool operator< (point z){return x<z.x||x==z.x&&y<z.y;}
    point operator- (point z){return point(x-z.x,y-z.y);}
};
inline ll d(point z, point w=point(0,0)){return (z.x-w.x)*(z.x-w.x)+(z.y-w.y)*(z.y-w.y);}
point tam[MX], cv[MX], u[MX], v[MX];
int N,T,top;
void input(){
    scanf("%d%d",&N,&T);
    for(int i=0;i<N;i++) scanf("%lld%lld%lld%lld",&u[i].x,&u[i].y,&v[i].x,&v[i].y);
}
void graham(){
    swap(tam[0],*min_element(tam,tam+N));
    for(int i=N;i--;) tam[i]=tam[i]-tam[0];
    sort(tam+1,tam+N,[](point m, point n){return m*n<0||m*n==0&&d(m)<d(n);});
    for(int i=top=0;i<N;i++){
        while(top>1&&(tam[i]-cv[top-2])*(cv[top-1]-cv[top-2])<=0) --top;
        cv[top++]=tam[i];
    }
}
ll RC(){
    int idx=0, jdx=max_element(cv,cv+top)-cv; ll D=0; point g, h;
    for(int i=0;i<top;i++){
        D=max(D,d(cv[idx],cv[jdx]));
        point g=cv[(idx+1)%top]-cv[idx], h=cv[(jdx+1)%top]-cv[jdx];
        (++(g*h>=0?idx:jdx))%=top;
    }
    return D;
}
ll pro(int t){
    for(int i=0;i<N;i++){
        tam[i].x=u[i].x+v[i].x*t;
        tam[i].y=u[i].y+v[i].y*t;
    }
    graham();
    return RC();
}
int main(){
    input();
    int p=0, q, r, s=T;
    while(p<s){
        q=p+(s-p)/3, r=s-(s-p)/3;
        if(pro(q)<=pro(r)) s=r-1;
        else p=q+1;
    }
    printf("%d\n%lld\n",p,pro(p));
}

Compilation message (stderr)

dist.cpp: In member function 'bool point::operator<(point)':
dist.cpp:11:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     bool operator< (point z){return x<z.x||x==z.x&&y<z.y;}
                                                  ^
dist.cpp: In lambda function:
dist.cpp:24:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     sort(tam+1,tam+N,[](point m, point n){return m*n<0||m*n==0&&d(m)<d(n);});
                                                               ^
dist.cpp: In function 'void input()':
dist.cpp:18:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&N,&T);
                        ^
dist.cpp:19:83: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0;i<N;i++) scanf("%lld%lld%lld%lld",&u[i].x,&u[i].y,&v[i].x,&v[i].y);
                                                                                   ^

• Subtask 1: 2 / 2
• Subtask 2: 40 / 40
• Subtask 3: 39 / 39
• Subtask 4: 19 / 19