?? usaco_5_1_1_fc.cpp
字號:
/*
PROB: fc
LANG: C++
*/
/*
檢驗凸包模板……
根據模板改良的Graham-Scan算法,用sort來實現nlgn的復雜度
*/
#include<iostream>
#include<memory>
#include<cmath>
#include<algorithm>
using namespace std;
const double INF = 1E200;
const double EP = 1E-10;
const int MAXV = 10001;
const double PI = 3.14159265;
/* 基本幾何結構 */
struct POINT
{
double x;
double y;
POINT(double a=0, double b=0) { x=a; y=b;} //constructor
};
struct LINESEG
{
POINT s;
POINT e;
LINESEG(POINT a, POINT b) { s=a; e=b;}
LINESEG() { }
};
struct LINE // 直線的解析方程 a*x+b*y+c=0 為統一表示,約定 a >= 0
{
double a;
double b;
double c;
LINE(double d1=1, double d2=-1, double d3=0) {a=d1; b=d2; c=d3;}
};
POINT Points[MAXV];
POINT ch[MAXV];
int n,m,len;
double dis;
void init()
{
int i,j,k;
freopen("fc.in","r",stdin);
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%lf%lf",&Points[i].x,&Points[i].y);
}
double dist(POINT p1,POINT p2) // 返回兩點之間歐氏距離
{
return( sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ) );
}
double multiply(POINT sp,POINT ep,POINT op)
{
return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y));
}
bool op(POINT a,POINT b)
{
if(multiply(a,b,Points[0])>0) return true;
else if(multiply(a,b,Points[0])==0 && dist(Points[0],a)<dist(Points[0],b)) return true;
return false;
}
void Graham_scan(POINT PointSet[],POINT ch[],int n,int &len)
{
int i,j,k=0,top=2;
POINT tmp;
// 選取PointSet中y坐標最小的點PointSet[k],如果這樣的點有多個,則取最左邊的一個
for(i=1;i<n;i++)
if ( PointSet[i].y<PointSet[k].y ||
(PointSet[i].y==PointSet[k].y) && (PointSet[i].x<PointSet[k].x) )
k=i;
tmp=PointSet[0];
PointSet[0]=PointSet[k];
PointSet[k]=tmp; // 現在PointSet中y坐標最小的點在PointSet[0]
/*for (i=1;i<n-1;i++) // 對頂點按照相對PointSet[0]的極角從小到大進行排序,極角相同的按照距離PointSet[0]從近到遠進行排序
{
k=i;
for (j=i+1;j<n;j++)
if ( multiply(PointSet[j],PointSet[k],PointSet[0])>0 || // 極角更小
(multiply(PointSet[j],PointSet[k],PointSet[0])==0) && // 極角相等,距離更短
dist(PointSet[0],PointSet[j])<dist(PointSet[0],PointSet[k]) )
k=j;
tmp=PointSet[i];
PointSet[i]=PointSet[k];
PointSet[k]=tmp;
}*/
sort(PointSet,PointSet+n,op);
ch[0]=PointSet[0];
ch[1]=PointSet[1];
ch[2]=PointSet[2];
for (i=3;i<n;i++)
{
while (multiply(PointSet[i],ch[top],ch[top-1])>=0) top--;
ch[++top]=PointSet[i];
}
len=top+1;
}
int main()
{
int i,j,k;
init();
Graham_scan(Points,ch,n,len);
for(i=0;i<len-1;i++)
dis+=dist(ch[i],ch[i+1]);
dis+=dist(ch[0],ch[len-1]);
freopen("fc.out","w",stdout);
printf("%0.2lf\n",dis);
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -