<题目链接>
题目大意：
给出一些点，让你求出将这些点全部围住需要的多长的绳子。
Andrew算法
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct node{
int x,y;
};
node vex[];
bool cmp1(node a,node b){
if(a.y==b.y)
return a.x<b.x;
else
return a.y<b.y;
}
int cross(node,node,node);
double dis(node,node);
bool cmp(node a,node b){
int m=cross(vex[],a,b);
if(m==)
return dis(vex[],a)-dis(vex[],b)<=?true:false;
else
return m>?true:false;
}
node stackk[];
int cross(node a,node b,node c){
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
double dis(node a,node b){
return sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y));
}
int main(){
int t;
while(scanf("%d",&t),t!=){
int i;
for(i=;i<t;i++){
scanf("%d%d",&vex[i].x,&vex[i].y);
}
if(t==)
printf("%.2f\n",0.00);
else if(t==)
printf("%.2f\n",dis(vex[],vex[]));
else{
sort(vex,vex+t,cmp1);
sort(vex+,vex+t,cmp);
memset(stackk,,sizeof(stackk));
stackk[]=vex[];
stackk[]=vex[];
int top=;
for(i=;i<t;i++){
while(i>=&&cross(stackk[top-],stackk[top],vex[i])<)
top--;
stackk[++top]=vex[i];
}
double s=;
for(i=;i<=top;i++)
s+=dis(stackk[i-],stackk[i]);
s+=dis(stackk[top],vex[]);
printf("%.2f\n",s);
}
}
}
2018-08-22