| ||||||||||
| 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