Surround the Trees:http://acm.hdu.edu.cn/showproblem.php?pid=1392
题意:
在给定点中找到凸包,计算这个凸包的周长。
思路:
这道题找出凸包上的点后,s数组中就是按顺序的点,累加一下距离就是周长了。
#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cassert> using namespace std;
//#pragma GCC optimize(3)
//#pragma comment(linker, "/STACK:102400000,102400000") //c++
#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue typedef long long ll;
typedef unsigned long long ull; typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int,pii> p3; //priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl '\n' #define OKC ios::sync_with_stdio(false);cin.tie(0)
#define FT(A,B,C) for(int A=B;A <= C;++A) //用来压行
#define REP(i , j , k) for(int i = j ; i < k ; ++i)
//priority_queue<int ,vector<int>, greater<int> >que; const ll mos = 0x7FFFFFFF; //
const ll nmos = 0x80000000; //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f; //
const int mod = ;
const double esp = 1e-;
const double PI=acos(-1.0); template<typename T>
inline T read(T&x){
x=;int f=;char ch=getchar();
while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x=f?-x:x;
} /*-----------------------showtime----------------------*/
const int maxn = ;
struct node
{
int x,y;
}p[maxn],s[maxn];
inline bool cmp(node a,node b){
double A = atan2((a.y - p[].y) , (a.x - p[].x));
double B = atan2((b.y - p[].y) , (b.x - p[].x));
if(A != B) return A < B;
else return a.x < b.x;
} ll Cross (node a,node b,node c){
return 1ll*(b.x - a.x)*(c.y - a.y) - 1ll*(b.y - a.y)*(c.x - a.x);
}
int top,n;
void Get(){
p[] = (node){inf,inf}; int k;
for(int i=; i<=n; i++)
if(p[].y > p[i].y || (p[].y == p[i].y && p[i].x < p[].x))
{
p[] = p[i]; k = i;
}
swap(p[k], p[]);
sort(&p[] , &p[n+], cmp);
s[] = p[] , s[] = p[], top = ;
for(int i=; i<=n; ){
if(top && Cross(s[top-] ,p[i], s[top]) >= )
top--;
else s[++top] = p[i++];
}
}
double dis(node a,node b){
return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
int main(){ while(~scanf("%d", &n) && n){
for(int i=; i<=n; i++){
scanf("%d%d", &p[i].x, &p[i].y);
}
Get(); double ans = ;
if(top == ){
ans = ;
}
else if(top == ){
ans = dis(s[],s[]);
}
else {
s[++top] = s[];
for(int i=; i<top; i++){
ans += dis(s[i], s[i+]);
}
} printf("%.2f\n", ans);
}
return ;
}
HDU - 1392