가장 먼 두점 거리 구하기 ; Prob No.0565 : 가장 먼 두 초소

rotating calipers (가장 먼 두 점 구하기)
http://koistudy.net/?mid=prob_page&NO=1381
 
이 문제는 돌아가는 캘리퍼스라는 알고리즘을 활용한 문제이다.
이 알고리즘을 쓰기 전에 convexhull algorithm으로 볼록 다각형을 구해놓아야 쓸 수 있다.
convexhull algorithm : 추후 설명하도록 하겠다.

가장 왼쪽 점과 가장 오른쪽 점에 각 각 접해있는 수직선인 두 calipers로 시작한다. 두 calipers는 항상 평행을 유지 해야한다.
 
calipers와 다각형 변이 이루는 두 각 중 작은 각 만큼 두 calipers를 시계 반대 방향으로 평행을 유지하도록 돌려준다.

다각형의 변과 캘리퍼스가 이루는 각은 변과 캘리퍼스를 벡터로 표현하고 벡터 사이각을 벡터 내적으로 구한다.
 
calipers과 접해있는 다각형의 꼭짓점 간의 거리 ( 초록색 선분 )중 최댓값이 가장 먼 두점의 거리가 된다..

 

이후 이 과정을 볼록 외피 꼭짓점 갯수 만큼 반복하여  caliper가 180도 돌아 처음 상태와 같아지도록 한다.

 

가장 먼 두 초소 풀이 convex hull ( O(nlogn) ) + rotating calipers ( O(n) )

!!!! 현재 " 가장 먼 두 초소" 데이터가 약해 convexhull 이후 rotating calipers가 아닌 n^2으로 가장 먼 두점 사이의 거리를 구해도 통과가 된다.

#include <bits/stdc++.h>
#define N 100010
#define SW 1
using namespace std;
typedef long long ll;
ll n,cnt,p1,p2,mx=0;
const double PI=acos(-1);
struct point{
    ll x,y;
    bool operator<(const point&r)const{
        return x<r.x||(x==r.x&&y<r.y);
    }
    ll ccw(point p,point q){ // 벡터 외적
        return (p.x-x)*(q.y-y)-(p.y-y)*(q.x-x);
    }
} a[N],convex[N];
void convexhull(){
    scanf("%lld",&n);
    ll i;
    for(i=1;i<=n;i++)
        scanf("%lld %lld",&a[i].x,&a[i].y);
    // sort O(nlogn)
    sort(a+1,a+1+n);
    //convexhull O(n)
    // convex에 볼록다각형의 꼭짓점 좌표를 저장한다.
    for(i=1;i<=n;i++){
        for(;cnt>=2&&convex[cnt-1].ccw(convex[cnt],a[i])<=0;--cnt);
        convex[++cnt]=a[i];
    }
    for(p2=cnt,i=n-1;i>=1;--i){
        for(;cnt>=p2+1&&convex[cnt-1].ccw(convex[cnt],a[i])<=0;--cnt);
        convex[++cnt]=a[i];
    }
// cnt는 볼록 외피 꼭짓점 갯수
    p1=1;cnt--;
}
ll cal_dis(){
    // 볼록 다각형 두 점 사이의 거리구하기
    return (convex[p1].x-convex[p2].x)*(convex[p1].x-convex[p2].x)+(convex[p1].y-convex[p2].y)*(convex[p1].y-convex[p2].y);
}
void rotating_calipers()
{
    ll i;
    ll x1,y1,x2,y2,xx1,yy1,xx2,yy2;
    double cos1,cos2;

 

   // x1과 y1은 왼쪽 캘리퍼스의 벡터, x2와 y2는 오른쪽 캘리퍼스이 벡터
    x1=x2=0;
    y1=-1,y2=1;
    //p1은 초기에 왼쪽에 있는 캘리퍼스가 볼록다각형의 접해있는 점, p2는 오른쪽에 있는 캘리퍼스가 다각형의 접해있는 점

    for(i=1;i<=cnt;i++){
        mx=max(mx,cal_dis());
        //다각형의 변의 벡터인 xx1,yy1,xx2,yy2를 구한다.
        xx1=(convex[p1%cnt+1].x-convex[p1].x);yy1=(convex[p1%cnt+1].y-convex[p1].y);
        xx2=(convex[p2%cnt+1].x-convex[p2].x);yy2=(convex[p2%cnt+1].y-convex[p2].y);
 
        //벡터의 내적으로 두 벡터 사이각의 코사인을 구한다.
        // 각도는 항상 180도 미만이므로 각이 작을 수록 코사인 값이 크다.
        cos1=(double)(x1*xx1+y1*yy1)/sqrt(x1*x1+y1*y1)/sqrt(xx1*xx1+yy1*yy1);
        cos2=(double)(x2*xx2+y2*yy2)/sqrt(x2*x2+y2*y2)/sqrt(xx2*xx2+yy2*yy2);
 
        if(cos1>cos2){// cos의 실수 오차를 없애고 싶으면 양변 제곱해서 통분 하면 된다.

            //왼쪽 캘리퍼스가 볼록 다각형에 접해있는 점(p1)을  반시계로  하나 이동 시키고
            // 다각형 변의 벡터가 캘리퍼스의 벡터가 된다.
            p1=p1%cnt+1;
            x1=xx1;y1=yy1;
 
            // 오른쪽 캘리퍼스는 왼쪽 캘리퍼스와 방향만 반대고 평행
            x2=-x1;y2=-y1;
        }
        else{

         //오른쪽 캘리퍼스가 볼록 다각형에 접해있는 점(p2)을  반시계로  하나 이동 시키고
            // 다각형 변의 벡터가 캘리퍼스의 벡터가 된다.
            p2=p2%cnt+1;
            x2=xx2;y2=yy2;
            x1=-x2;y1=-y2;
        }
    }
    printf("%lld\n",mx);
}
int main(){
    convexhull();
    rotating_calipers();
}