Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
加了备注的程序求改- - 第一个凸包程序实在压力大#include <cstdio> #include <iostream> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> using namespace std; const int max_n = 10000 + 10; int n; struct point { double x, y; point(double a, double b):x(a), y(b){} point():x(0),y(0){} }t0; vector<point>q; vector<point>::iterator qit, tit; vector<int>stack; double operator - (point A, point B)//返回a-b的距离的平方 { return pow((A.x - B.x),2) + pow((A.y - B.y),2); } double cross(point T, point A, point B) // T->A 向量 和T->B向量的叉积 { return (A.x - T.x) * (B.y - T.y) - (B.x - T.x) * (A.y - T.y); } bool operator < (point A, point B) // sort的比较函数 用重载运算符 { double tmp = cross(t0, A, B); if (tmp == 0) return (A - t0) < (B - t0); return tmp > 0; } int main() { scanf("%d", &n); for (int i = 0; i != n; ++ i) { double x, y; scanf("%lf%lf",&x, &y); q.push_back(point(x, y)); } tit = q.begin(); for (qit = q.begin(); qit != q.end(); ++ qit) // 找出最小值 if ((qit -> x < tit -> x) || ((qit -> x == tit -> x) && (qit -> y < tit -> y))) tit = qit; t0 = *tit; //t0保存最小的坐标 sort(q.begin(), q.end()); //按照极角排序 stack.push_back(0); //起点和第一个点入栈 stack.push_back(1); for (int i = 2; i != n; ++ i) { while (stack.size() > 1 && cross( q[stack[stack.size() - 2]] , q[stack[stack.size()-1]], q[i]) < 0 ) //栈内元素大于等于2个 叉积<0 { stack.pop_back(); //退栈 } stack.push_back(i); //把当前点进栈 } int ans = 0; for (int i = 2; i != stack.size(); ++ i) //计算凸包面积 { ans += cross(t0, q[stack[i - 1]], q[stack[i]]); } ans += cross(t0, q[stack[stack.size() - 1]], q[stack[1]]); cout<<ans / 50 <<endl; return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator