二维凸包（模板） hdu 1348 求凸包的周长

  1 const int N =1010;
  2 const double PI = 3.1415927;
  3 double EPS=1e-10;
  4 // 考虑误差的加法运算
  5 double add(double a,double b)
  6 {
  7     if(fabs(a+b)<EPS*(fabs(a)+fabs(b))) return 0;
  8     return a+b;
  9 }
 10 struct Point{
 11     double x,y;
 12     Point(){}
 13     Point(double x,double y):x(x),y(y){} // 构造函数，方便代码编写
 14     Point(const Point & p):x(p.x),y(p.y){}
 15     Point operator +(Point p){
 16         return Point(add(x,p.x), add(y,p.y));
 17     }
 18     Point operator-(Point p){
 19         return Point(add(x,-p.x),add(y,-p.y));
 20     }
 21     Point operator*(double d){
 22         return Point(x*d,y*d);
 23     }
 24     double operator*(Point p){  // 内积 点乘
 25         return add(x*p.x, y*p.y);
 26     }
 27     double operator^(Point p){//  外积 叉乘
 28         return add(x*p.y,-y*p.x);
 29     }
 30     friend ostream& operator<<(ostream& os,const Point& p ){
 31         os<<p.x<<" "<<p.y<<endl;
 32         return os;
 33     }
 34     friend istream& operator>>(istream& is, Point& rh) {// Point 不能是常量，是变量
 35         is>>rh.x>>rh.y;
 36         return is;
 37     }
 38     double dist(Point p){
 39         return sqrt( add( (x-p.x)*(x-p.x),(y-p.y)* (y-p.y) ) );
 40     }
 41 };
 42 
 43 Point List[N];   // 输入点集Q
 44 Point stack[N];  // 栈从低到顶部包含了按逆时针方向排列在CH(Q)(凸包)中的各个顶点。
 45 int top;   // 栈顶
 46 
 47 
 48 // 按极角排序，如果极角相等则按距离从小到大，sort是按从小到大排列的，故需对<符号重载
 49 bool operator<(Point p1,Point p2)
 50     {
 51     double  tmp=(p1-List[0])^(p2-List[0]); //List[0]为基点
 52     if(tmp>0) return 1;
 53     else if(tmp==0 && p1.dist(List[0])< p2.dist(List[0])) return 1;
 54     else return 0;
 55     }
 56 
 57 // 输入点集Q，并把最左下方的点放在 LIst[0]，作为基点，
 58 //并且进行极角排序,对sort(list+1,List+n) ，最大时间O(nlgn)
 59 void init(int n)
 60 {
 61     Point p0;
 62     int flag=0;
 63     cin>>List[0];
 64     p0.x=List[0].x;
 65     p0.y=List[0].y;
 66     for(int i=1;i<n;i++)
 67     {
 68         cin>>List[i];
 69         if((p0.y> List[i].y ) || ((p0.y==List[i].y )&& (p0.x> List[i].x)))
 70         {
 71             p0.x=List[i].x;
 72             p0.y=List[i].y;
 73             flag=i;
 74         }
 75     }
 76     List[flag]=List[0];
 77     List[0]=p0;
 78     sort(List+1,List+n);
 79 }
 80 // 寻找凸包 graham 扫描法 时间O(n)
 81 void graham(int n)
 82 {
 83     if(n==1)
 84         {top=0;
 85         stack[0]=List[0];}
 86     if(n==2)
 87     {
 88         top=1;
 89         stack[0]=List[0];
 90         stack[1]=List[1];
 91     }
 92     if(n>2)
 93     {
 94         for(int i=0;i<=1;i++)  // 初始化栈，有p0，p1进栈
 95             stack[i]=List[i];
 96         top=1;
 97         for(int i=2;i<n;i++)
 98         {
 99             while(top>=1 && ((stack[top]-stack[top-1])^(List[i]-stack[top-1]))<=0) // 非左转
100                 top--; // 删除栈顶元素
101             top++;
102             stack[top]=List[i]; // 将i压入栈
103         }
104     }
105 }

#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int N =1010;
const double PI = 3.1415927;
double EPS=1e-10;
// 考虑误差的加法运算
double add(double a,double b)
{
    if(fabs(a+b)<EPS*(fabs(a)+fabs(b))) return 0;
    return a+b;
}
struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){} // 构造函数，方便代码编写
    Point(const Point & p):x(p.x),y(p.y){}
    Point operator +(Point p){
        return Point(add(x,p.x), add(y,p.y));
    }
    Point operator-(Point p){
        return Point(add(x,-p.x),add(y,-p.y));
    }
    Point operator*(double d){
        return Point(x*d,y*d);
    }
    double operator*(Point p){  // 内积 点乘
        return add(x*p.x, y*p.y);
    }
    double operator^(Point p){//  外积 叉乘
        return add(x*p.y,-y*p.x);
    }
    friend ostream& operator<<(ostream& os,const Point& p ){
        os<<p.x<<" "<<p.y<<endl;
        return os;
    }
    friend istream& operator>>(istream& is, Point& rh) {// Point 不能是常量，是变量
        is>>rh.x>>rh.y;
        return is;
    }
    double dist(Point p){
        return sqrt( add( (x-p.x)*(x-p.x),(y-p.y)* (y-p.y) ) );
    }
};

Point List[N];   // 输入点集Q
Point stack[N];  // 栈从低到顶部包含了按逆时针方向排列在CH(Q)(凸包)中的各个顶点。
int top;   // 栈顶


// 按极角排序，如果极角相等则按距离从小到大，sort是按从小到大排列的，故需对<符号重载
bool operator<(Point p1,Point p2)
    {
    double  tmp=(p1-List[0])^(p2-List[0]); //List[0]为基点
    if(tmp>0) return 1;
    else if(tmp==0 && p1.dist(List[0])< p2.dist(List[0])) return 1;
    else return 0;
    }

// 输入点集Q，并把最左下方的点放在 LIst[0]，作为基点，
//并且进行极角排序,对sort(list+1,List+n) ，最大时间O(nlgn)
void init(int n)
{
    Point p0;
    int flag=0;
    cin>>List[0];
    p0.x=List[0].x;
    p0.y=List[0].y;
    for(int i=1;i<n;i++)
    {
        cin>>List[i];
        if((p0.y> List[i].y ) || ((p0.y==List[i].y )&& (p0.x> List[i].x)))
        {
            p0.x=List[i].x;
            p0.y=List[i].y;
            flag=i;
        }
    }
    List[flag]=List[0];
    List[0]=p0;
    sort(List+1,List+n);
}
// 寻找凸包 graham 扫描法 时间O(n)
void graham(int n)
{
    if(n==1)
        {top=0;
        stack[0]=List[0];}
    if(n==2)
    {
        top=1;
        stack[0]=List[0];
        stack[1]=List[1];
    }
    if(n>2)
    {
        for(int i=0;i<=1;i++)  // 初始化栈，有p0，p1进栈
            stack[i]=List[i];
        top=1;
        for(int i=2;i<n;i++)
        {
            while(top>=1 && ((stack[top]-stack[top-1])^(List[i]-stack[top-1]))<=0) // 非左转
                top--; // 删除栈顶元素
            top++;
            stack[top]=List[i]; // 将i压入栈
        }
    }
}
int main() {
    int T,count=0,n;
    double r;
    cin>>T;
    while(T--)
    {
        if(count) cout<<endl;
        count=1;
        cin>>n>>r;
        init(n);
        graham(n);
        double ans=0;
        for(int i=0;i<top;i++)
            ans+=stack[i].dist(stack[i+1]);
        ans+=stack[top].dist(stack[0]);
        ans+=2*PI*r;
        printf("%.0lf\n",ans);
    }
    return 0;
}