p1113.cpp

大概POJ上50道比较难的题的代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 10000;
const double PI = acos(-1.0);
const double EPS = 1e-7;
struct Point{
    double x,y;
};
struct TPoint{
    double x,y,ang;
};
Point S[MAXN];
Point CS[MAXN];
TPoint T[MAXN];
int n,sp;
double ARGUMENT(double x,double y){
    if(x>0){
        if(y>0) return atan(y/x);
        if(y==0) return atan(0.0);
        if(y<0) return 2*PI+atan(y/x);
    }
    if(x==0){
        if(y>0) return PI*0.5;
        if(y<0) return PI*1.5;
    }
    if(x<0){
        if(y>0) return PI+atan(y/x);
        if(y==0) return PI;
        if(y<0) return PI+atan(y/x);
    }
}
bool cmp(TPoint a ,TPoint b){
    return a.ang < b.ang - EPS || (fabs(a.ang - b.ang) < EPS && pow(a.x,2.0)+pow(a.y,2.0) < pow(b.x,2.0)+pow(b.y,2.0));
}
void convex_hull(Point S[],Point CS[],int n,int& sp){
    int k,i;
    double D;
    for(i = 1;i < n;++i)
        if(S[i].y < S[0].y || (fabs(S[i].y - S[0].y) <= EPS && S[i].x < S[0].x))
            swap(S[i],S[0]);
    for(i = 1;i < n;++i){
        T[i-1].x = S[i].x - S[0].x;
        T[i-1].y = S[i].y - S[0].y;
        T[i-1].ang = ARGUMENT(T[i-1].x,T[i-1].y);
    }
    sort(T,T+n-1,cmp);
    sp = 1; k = 1;
    CS[0].x = 0.0; CS[0].y = 0.0;
    CS[1].x = T[0].x; CS[1].y = T[0].y;
    while(k < n){
        D = (CS[sp].x - CS[sp-1].x) * (T[k].y - CS[sp-1].y) -
            (CS[sp].y - CS[sp-1].y) * (T[k].x - CS[sp-1].x);
        if(D >= 0){
            ++sp;
            CS[sp].x = T[k].x; CS[sp].y = T[k].y;
            ++k;
        }
        else sp--;
    }
}
inline double Dis(Point a,Point b){
	return sqrt(pow(a.x - b.x,2.0) + pow(a.y - b.y,2.0));
}

int main(){
    int i,n;
	double res,l;
    Point S[MAXN],CS[MAXN];
    cin >> n >> l;
    for(i = 0;i < n;++i) cin >> S[i].x >> S[i].y;
    convex_hull(S,CS,n,sp);
	res = Dis(CS[0],CS[sp-1]) + 2.0 * PI * l;
    for(i = 0;i < sp-1;++i)
       res += Dis(CS[i],CS[i+1]);
	for(i = 1;i < sp-1;++i)
		if(fabs(ARGUMENT(CS[i].x,CS[i].y) - ARGUMENT(CS[i+1].x,CS[i+1].y)) >= EPS) break;
	if(i == sp - 1) res -= Dis(CS[sp-1],CS[0]);
	printf("%.0lf\n",res);
}