백준 1310번 달리기 코스 (boj/1310.cpp)

Convex Hull Algorithm을 사용합니다.

알고리즘으로 외곽껍질을 구한 다음, 그 껍질을 돌면서 값을 찾습니다.

그냥 동적계획법 두 번 쓴거라 생각하면 마음이 편합니다.

공간복잡도는 N, 시간복잡도는 NlogN이 되겠습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define INF 110000
using namespace std;
vector< pair< double, double > > coor;
vector< pair< double, int > > pq;
vector< int > cha;
double dst(pair<double, double> fir, pair<double, double> sec){ return sqrt(pow(fir.first-sec.first, 2) + pow(fir.second-sec.second, 2)); }
double ccw(pair<double, double> fir, pair<double, double> sec, pair<double, double> end){
    pair<double, double> v1, v2;
    double res, tmp;
    v1 = make_pair(sec.first-fir.first, sec.second-fir.second);
    v2 = make_pair(end.first-sec.first, end.second-sec.second);
    res = v1.first*v2.second - v1.second*v2.first;
    tmp = dst(fir, sec)*dst(sec, end);
    return res/tmp;
}
int main(void){
    int N, sze;
    double x, y;
    double res, tmp;
    int anc, hok;
    pair<double, double> end;
    cin >> N;
    for(int i=0;i<N;i++){ cin >> x >> y; coor.push_back(make_pair(x, y)); }
    sort(coor.begin(), coor.end());
    x=coor[0].first; y=coor[0].second; pq.push_back(make_pair(-INF, 0));
    for(int i=1;i<N;i++){ pq.push_back(make_pair((coor[i].second-y)/(coor[i].first-x), i)); }
    sort(pq.begin()+1, pq.end());
    sze=2; cha.push_back(0); cha.push_back(pq[1].second);
    for(int i=2;i<N;i++){
        for(end=coor[pq[i].second];sze>=2 && ccw(coor[cha[sze-2]], coor[cha[sze-1]], end)<=0; sze--){ cha.pop_back(); }
        cha.push_back(pq[i].second); sze++; }
    anc=0; hok=1;
    for(;anc!=hok;anc++){
        tmp=dst(coor[cha[anc]], coor[cha[hok]]); if(res<tmp){ res=tmp; }
        if(hok+1<sze && tmp<dst(coor[cha[anc]], coor[cha[hok+1]])){ hok++; anc--; } }
    res*=res;
    cout << (long long)(res+0.5);
    return 0;
}