程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDOJ 2202 最大三角形 凸包旋轉卡殼求最大三角形面積

HDOJ 2202 最大三角形 凸包旋轉卡殼求最大三角形面積

編輯:關於C++


凸包旋轉卡殼求最大三角形面積

最大三角形

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3316 Accepted Submission(s): 1119


Problem Description 老師在計算幾何這門課上給Eddy布置了一道題目,題目是這樣的:給定二維的平面上n個不同的點,要求在這些點裡尋找三個點,使他們構成的三角形擁有的面積最大。
Eddy對這道題目百思不得其解,想不通用什麼方法來解決,因此他找到了聰明的你,請你幫他解決這個題目。
Input 輸入數據包含多組測試用例,每個測試用例的第一行包含一個整數n,表示一共有n個互不相同的點,接下來的n行每行包含2個整數xi,yi,表示平面上第i個點的x與y坐標。你可以認為:3 <= n <= 50000 而且 -10000 <= xi, yi <= 10000.
Output 對於每一組測試數據,請輸出構成的最大的三角形的面積,結果保留兩位小數。
每組輸出占一行。

Sample Input
3
3 4
2 6
3 7
6
2 6
3 9
2 0
8 0
6 6
7 7

Sample Output
1.50
27.00

Author Eddy


/* ***********************************************
Author        :CKboss
Created Time  :2014年12月28日 星期日 19時28分15秒
File Name     :HDOJ2202.cpp
************************************************ */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

struct Point
{
	double x,y;
	Point operator - (Point a) const
	{
		return (Point){x-a.x,y-a.y};
	}
	bool operator < (Point a) const
	{
		if(x!=a.x) return x vp;
vector ch;

void CovexHull(vector &p)
{
	sort(p.begin(),p.end());
	p.erase(unique(p.begin(),p.end()),p.end());
	int n=p.size();
	m=0;
	ch=vector(n+1);
	for(int i=0;i1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<0) m--;
		ch[m++]=p[i];
	}
	int k=m;
	for(int i=n-2;i>=0;i--)
	{
		while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<0) m--;
		ch[m++]=p[i];
	}
	if(n>1) m--;
	ch.resize(m);
}

double Rotating_Calipers(vector& p,int n)
{
	double ans=0;
	for(int i=0;i


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved