首页 > ACM题库 > HDU-杭电 > hdu 2299 Largest Triangle[解题报告]C++
2014
01-05

hdu 2299 Largest Triangle[解题报告]C++

Largest Triangle

问题描述 :

You have a convex polygon. You select three consecutive vertices and create a triangle with them. Remove this triangle from the polygon (if you had a polygon with N vertices, the resulting polygon would have N-1 vertices). Repeat this process until the remaining polygon is a triangle.
You are given the vertices of the polygon in clockwise order. Output the largest possible triangle that can remain at the end.

输入:

There are multiple cases (no more than 150).
The first line of each case is an integer n indicating the number of vertices in this polygon (3 <= n && n <= 50).
Then n lines follow, each with two integers x y (0 <= x <= 100, 0 <= y <= 100), giving the cordinate of the vertices.

输出:

There are multiple cases (no more than 150).
The first line of each case is an integer n indicating the number of vertices in this polygon (3 <= n && n <= 50).
Then n lines follow, each with two integers x y (0 <= x <= 100, 0 <= y <= 100), giving the cordinate of the vertices.

样例输入:

3
1 1
2 3
3 2

4
1 1
1 2
3 3
2 1

样例输出:

1.5
1.5

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <list>
#include <queue>
#include <stack>
#include <cmath>

using namespace std;

#define PF(x) (scanf("%d",&x))
#define PT(x,y) (scanf("%d%d",&x,&y))
#define PR(x) (printf("%d\n",x))
#define PRT(x,y)(printf("%d %d\n",x,y))
#define M 1000

int n;
struct P
{
	int x,y;
	void in()
	{
		PT(x,y);
	}
};
P ar[1000];

int mul(P a,P b,P c)
{
	return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
double area(P a,P b,P c)
{
	return fabs((double)mul(a,b,c))/2.0;
}
void init()
{
    while(scanf("%d",&n)!=EOF)
	{
		for(int i=0;i<n;i++)
			ar[i].in();

		double areas = 0.0;
		for(int i=0;i<n;i++)
			for(int j = i+1;j<n;j++)
				for(int k = j+1;k<n;k++)
				{
					if(areas<area(ar[i],ar[j],ar[k]))
						areas = area(ar[i],ar[j],ar[k]);
				}
				printf("%.1lf\n",areas);
	}
	return ;
}
int main()
{
	init();
	return 0;
}