首页 > 代码库 > HDU 1392 Surround the Trees
HDU 1392 Surround the Trees
PS: 在求解两个点的时候就是两个点的距离,在这WA了一次。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <cmath> using namespace std; const int maxn = 110; struct point { int x, y; point(double x=0, double y=0):x(x),y(y) {} }; point operator - (point A, point B) { return point(A.x-B.x, A.y-B.y); } double Dist(point A, point B) { double x = (A.x-B.x)*(A.x-B.x); double y = (A.y-B.y)*(A.y-B.y); return sqrt(x+y); } point ch[maxn]; vector<point> v; int n; double Cross(point A, point B) { return A.x*B.y - A.y*B.x; } bool cmp(point a, point b) { if(a.x!=b.x) return a.x < b.x; else return a.y<b.y; } int ConvexHull() { int m = 0; for(int i = 0; i < n; i++) { while(m>1 && Cross(ch[m-1]-ch[m-2], v[i]-ch[m-2])<=0) m--; ch[m++] = v[i]; } int k = m; for(int i = n-2; i >= 0; i--) { while(m>k && Cross(ch[m-1]-ch[m-2], v[i]-ch[m-2])<=0) m--; ch[m++] = v[i]; } if(n>1) m--; return m; } int main() { point t; while(scanf("%d", &n) && n) { v.clear(); for(int i = 0; i < n; i++) { scanf("%d%d", &t.x, &t.y); v.push_back(t); } sort(v.begin(), v.end(), cmp); int m = ConvexHull(); double res = 0; if(m==2) { res = Dist(ch[0], ch[1]); printf("%.2lf\n", res); // res*2 WA. continue; } for(int i = 0; i < m-1; i++) { res += Dist(ch[i], ch[i+1]); } res += Dist(ch[m-1], ch[0]); printf("%.2lf\n", res); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。