欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ - 1113 - Wall (凸包)

程序员文章站 2022-03-29 21:19:30
...

链接:

http://poj.org/problem?id=1113

题意:

求凸包,外加圆的周长

思路:

板子:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const double eps = 1e-7;
const double PI = 3.1415926;
struct Point
{
    double x,y;
    Point(double x =0,double y = 0):x(x),y(y) {}
};
int n ;
Point p[1200],s[1200];
double cross(Point a,Point b, Point c)
{
    return ((b.x - a.x) *(c.y-a.y)- (b.y - a.y)*(c.x - a.x));
}
double dis(Point a,Point b)
{
    return sqrt((a.x- b.x)*(a.x - b.x)+(b.y - a.y)*(b.y-a.y));
}
bool cmp(Point a,Point b)
{
    if(a.x != b.x ) return a.x < b.x;
    else
        return a.y < b.y;
}
bool cmp1(Point a,Point b)
{
    double m =cross(p[0],a,b);
    if(fabs(m- 0.0) <= eps)
    {
        if(dis(p[0],b)>dis(p[0],a))return true;
        return false;
    }
    else
    {
        if(m > 0) return true;
        else return false;
    }
}
int main()
{
    double l;
    while(cin>>n>>l)
    {
        for(int i = 0; i < n; i++)
            cin>>p[i].x>>p[i].y;
        sort(p,p+n,cmp);
        sort(p,p+n,cmp1);
        s[0].x = p[0].x;
        s[0].y = p[0].y;
        s[1].x = p[1].x;
        s[1].y = p[1].y;
        int top = 1;
        for(int i = 2; i < n; i++)
        {
            while(top>=1 && cross(s[top-1],s[top],p[i]) < 0)top--;
            s[++top] = p[i];
        }
        double sum = 0;
        for(int i = 0; i < top; i++)
            sum += dis(s[i],s[i+1]);
        sum += dis(s[0],s[top]);
        sum +=(2*PI*l);
        printf("%.f\n",sum);
    }
    return 0;
}