UVA 218 Moth Eradication【顺时针输出凸包顶点+凸包周长】

周长】"/>

UVA 218 Moth Eradication【顺时针输出凸包顶点+凸包周长】

题目大意：如题顺时针输出凸包顶点，并且输出凸包周长；

                    注意：（1）题目告诉输出时，凸包起点任意，但必须输出两次；

                                （2）每两组数据之间换行，其他就没什么了。

解题策略：同上。

/*UVA 218 Moth EradicationAC by J_DarkON 2013/5/6 16:22Time 0.042s
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
/
struct point{double x, y;point(double a, double b){x = a;y = b;}double Distance(point t){return sqrt((x-t.x)*(x-t.x) + (y-t.y)*(y-t.y));}
};
vector<point> p;
vector<int> CH; //存放凸包顶点序号   模拟栈
int testCase, top, cc=0, nodeNum;
/
void Input(){p.clear();CH.clear();CH.resize(nodeNum+5);double xx, yy;for(int i=0; i<nodeNum; i++){cin >> xx >> yy;p.push_back(point(xx, yy));}
}bool cmp(point a, point b){if(a.y == b.y)  return a.x < b.x;return a.y < b.y;
}bool turnRight(point px1, point px2, point pp){const double eps = 1e-20;if((px2.x - px1.x)*(pp.y - px2.y) - (pp.x - px2.x)*(px2.y - px1.y) <= eps) return true;return false;
}
void Compute(){sort(p.begin(), p.end(), cmp);CH[0] = 0;CH[1] = 1;top = 1;//从起点0到到排序最后点作凸包右链  过程1for(int i=2; i<nodeNum; i++){while( top && turnRight(p[CH[top-1]], p[CH[top]], p[i]) ){top--;}CH[++top] = i;}int len = top;//从排序最高点到到起点0fab反向作凸包右链  过程2CH[++top] = nodeNum-2;for(int i=nodeNum-3; i>=0; i--){//top!=len, 不考虑已在过程1生成凸包上的点while( top!=len && turnRight(p[CH[top-1]], p[CH[top]], p[i]) ){top--;}CH[++top] = i;}
}void Output(){int sPos;double Perimeter = 0;if(cc > 0)  cout << endl;printf("Region #%d:\n", ++cc);//顺时针输出凸包for(sPos=0; sPos<top; sPos++){if(p[CH[sPos]].x == p[0].x && p[CH[sPos]].y == p[0].y)break;}for(int i=top-1; i>=sPos; i--){if(i!=top-1)  printf("-");printf("(%.1lf,%.1lf)", p[CH[i]].x, p[CH[i]].y);if(i!=sPos)  Perimeter += p[CH[i]].Distance(p[CH[i-1]]);else Perimeter += p[CH[sPos]].Distance(p[CH[top-1]]);}printf("-(%.1lf,%.1lf)\n", p[CH[top-1]].x, p[CH[top-1]].y);printf("Perimeter length = %.2lf\n", Perimeter);}/
int main(){while(cin >> nodeNum && nodeNum){Input();Compute();Output();}return 0;
}