首页 > 代码库 > 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-计算几何
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。