题意:给你一些点,求这些点组成的三角形面积最大,而且三角形内不能包含其他点
#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;
}