Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

加了备注的程序求改- - 第一个凸包程序实在压力大

Posted by xyf at 2014-11-16 21:38:44 on Problem 3348
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator