首页 > 代码库 > uva-10112-计算几何

uva-10112-计算几何

题意:给你一些点,求这些点组成的三角形面积最大,而且三角形内不能包含其他点

 

#include <iostream>#include <math.h>#include<stdio.h>using namespace std;struct Node{	char c;	int x;	int y;};void sort(Node nodes[3], int length){	for (int i = 0; i < length; i++)	{		for (int j = 1; j < length - i; j++)		{			if (nodes[j - 1].c > nodes[j].c)			{				Node temp = nodes[j];				nodes[j] = nodes[j - 1];				nodes[j - 1] = temp;			}		}	}}double area(double x1, double y1, double x2, double y2, double x3, double y3){	double i = (y3 - y1) * (x2 - x1) - (y2 - y1) * (x3 - x1);	return fabs(i) * 0.5;}int main(){	while (true)	{		int n;		cin >> n;		if (!n)			return 0;		Node* nodes = new Node[n];		Node res[3];		for (int i = 0; i < n; i++)		{			Node node;			cin >> node.c >> node.x >> node.y;			nodes[i] = node;		}		double maxa = -1;		for (int i = 0; i < n; i++)		{			for (int j = i + 1; j < n; j++)			{				for (int k = j + 1; k < n; k++)				{					double a = area(nodes[i].x, nodes[i].y, nodes[j].x,							nodes[j].y, nodes[k].x, nodes[k].y);					if (a <= maxa)						continue;					int contain = false;					for (int t = 0; t < n; t++)					{						if(t == i || t == j || t == k)							continue;						double s1, s2, s3;						s1 = area(nodes[t].x, nodes[t].y, nodes[j].x,								nodes[j].y, nodes[k].x, nodes[k].y);						s2 = area(nodes[i].x, nodes[i].y, nodes[t].x,								nodes[t].y, nodes[k].x, nodes[k].y);						s3 = area(nodes[i].x, nodes[i].y, nodes[j].x,								nodes[j].y, nodes[t].x, nodes[t].y);						if ((s1 + s2 + s3) == a)						{							contain = true;							break;						}					}					if (!contain)					{						res[0] = nodes[i];						res[1] = nodes[j];						res[2] = nodes[k];						maxa = a;					}				}			}		}		sort(res, 3);		cout << res[0].c << res[1].c << res[2].c << endl;	}	return 0;}

  

uva-10112-计算几何