BOJ 13310 - 먼 별

문제 링크 : https://www.acmicpc.net/problem/13310

문제 태그

삼분 탐색, 로테이팅 켈리퍼스, 볼록 껍질

문제 풀이

가장 멀리 떨어진 두 별의 거리가 최소인 날을 구해야 한다. 다시 생각하면 임의의 두 별에 대해서 거리를 구한 후, 그 중 최댓값이 그 날에 대한 수치가 되는 것이다. 문제에서는 각 날별로 두 별의 거리를 구하는 것이지만 일단 관점을 바꿔서 두 별의 거리를 각 날별로 관찰해보자.

V자. 이런식으로 나올것이다. 즉, 일정 시점까지는 두 별이 계속 가까워 졌다가, 일정 시점 이후부터는 계속 멀어질 것이다. 혹은 시간 구간 내에서는 계속 감소하거나 계속 증가할 수도 있다.

두 별에 대한 모든 거리 그래프를 겹친 후에 그 중 최댓값을 뽑아낸 그래프 G'를 생각해보자. 그러면 아래로 볼록한 그래프가 나오게 된다. 정확히 아래로 볼록한 그래프가 아니라 정확히 말하자면 G'에서 최소점의 x위치를 알 수 있고 임의의 두 위치에 대해서 x<x1<x2면 f(x1)<=f(x2) 이고, x2<x1<x 여도 f(x1)<=f(x2)이다. 그림으로 그리면 아래와 같이 나오게 된다. 

이런 형태의 그래프에서 최소점을 구하는 것은 삼분 탐색으로 가능함이 잘 알려져 있다. 하지만 삼분 탐색을 하기 위해서는 함수값을 구할 수 있어야 한다. 즉, 이 문제에서는 각 날 별로 가장 먼 두 별 사이의 거리를 구할 수 있어야 한다는 것이다. 하지만 이 문제는 $O(NlgN)$이 잘 알려져 있다. (문제 - 고속도로) 따라서 최종 문제는 $O(NlgNlgT)$에 해결할 수 있다. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
struct poi{
    ll x,y;
};
 
ll ccw(poi a,poi m,poi b)
{
    ll t=(a.x-m.x)*(b.y-m.y)-(a.y-m.y)*(b.x-m.x);
    return (t<0)-(t>0);
}
 
ll cccw(poi a,poi b,poi c,poi d){
    d.x-=(c.x-b.x);
    d.y-=(c.y-b.y);
    return ccw(a,b,d);
}
 
ll dist(poi a,poi b)
{
    return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);
}
 
poi bas[1010101];
poi cha[1010101];
poi arr[1010101];
 
bool sf(poi a,poi b){
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
 
bool sf2(poi a,poi b){
    return (ccw(arr[1],a,b)>0||(ccw(arr[1],a,b)==0&&dist(arr[1],a)<dist(arr[1],b)));
}
 
poi ch[1010101];
ll far[1010101];
 
ll sol(ll n, ll k){
    ll i,j,l,m;
 
    for(i=1;i<=n;i++){
        arr[i].x=bas[i].x+k*cha[i].x;
        arr[i].y=bas[i].y+k*cha[i].y;
    }
 
    sort(arr+1,arr+1+n,sf);
    sort(arr+2,arr+1+n,sf2);
    ch[0]=arr[1];
    ch[1]=arr[2];
    ll fl=2;
    ll cnt=2;
    for(i=3;i<=n;i++){
        while(fl>=2&&ccw(ch[fl-2],ch[fl-1],arr[i])<=0)
            fl--;
        ch[fl]=arr[i];
        fl++;
    }
 
    ll fl2=1;
    ll ans=0;
    for(i=0;i<fl;i++){
        while((fl2+1)!=i&&cccw(ch[i],ch[i+1],ch[fl2%fl],ch[(fl2+1)%fl])>0){
            if(ans<dist(ch[i],ch[fl2%fl])){
            ans=dist(ch[i],ch[fl2%fl]);
        }
            fl2++;
        }
        //printf("%lld %lld\n",i,fl2);
        if(ans<dist(ch[i],ch[fl2%fl])){
            ans=dist(ch[i],ch[fl2%fl]);
        }
    }
    return ans;
}
 
int main(){
    ll i,j,k,l,m,n,t;
    scanf("%lld %lld",&n,&t);
    for(i=1;i<=n;i++){
        scanf("%lld %lld %lld %lld",&bas[i].x,&bas[i].y,&cha[i].x,&cha[i].y);
    }
    ll lo=0,hi=t;
    while(lo+10<hi){
        ll mid1=(lo+lo+hi)/3;
        ll mid2=(lo+hi+hi)/3;
        if(sol(n,mid1)<=sol(n,mid2)) hi=mid2;
        else lo=mid1;
    }
    ll ans=1e18;
    ll pos=0;
    for(i=lo;i<=hi;i++){
        if(ans>sol(n,i)){
            ans=sol(n,i);
            pos=i;
        }
    }    
    printf("%lld %lld",pos,ans);
}