leetcode-go/poj/1569.myacm-triangles/main.cc

#include <cmath>
#include <cstdio>

#define Vector Point

using namespace std;

const int N = 15;

struct Point {
  double x;
  double y;
  Point(double x = 0, double y = 0) : x(x), y(y){};
} point[N];

double operator^(const Vector &v1, const Vector &v2) {
  return v1.x * v2.y - v1.y * v2.x;
}

Vector operator-(const Vector &v1, const Vector &v2) {
  return Vector(v1.x - v2.x, v1.y - v2.y);
}

Vector operator+(const Vector &v1, const Vector &v2) {
  return Vector(v1.x + v2.x, v1.y + v2.y);
}

Vector operator*(double k, const Vector &v) { return Vector(k * v.x, k * v.y); }

int which_side(const Vector &v1, const Vector &v2) {
  double res = v1 ^ v2;
  if (res == 0) return 0;
  if (0 < res) return 1;
  return -1;
}

double area_of(const Vector &v1, const Vector &v2) { return fabs(v1 ^ v2) / 2; }

int main() {
  int n;
  char p1, p2, p3, str[2];
  while (scanf("%d", &n) != EOF) {
    if (n == 0) break;
    double max_area = 0;
    for (int i = 0; i < n; i++)
      scanf("%s %lf %lf", str, &point[i].x, &point[i].y);
    for (int i = 0; i < n - 2; i++) {
      for (int j = i + 1; j < n - 1; j++) {
        for (int k = j + 1, side, l; k < n; k++) {
          Point &a = point[i];
          Point &b = point[j];
          Point &c = point[k];
          Vector v1 = c - a, v2 = a - b, v3 = b - c;
          side = ((a - b) ^ (c - b)) < 0 ? -1 : 1;
          for (l = 0; l < n; l++) {
            if (l == i || l == j || l == k) continue;
            Point &p = point[l];
            int s1 = which_side(v1, p - a);
            int s2 = which_side(v2, p - b);
            int s3 = which_side(v3, p - c);
            if ((s1 == 0 || s1 == side) && (s2 == 0 || s2 == side) &&
                (s3 == 0 || s3 == side))
              break;
          }
          if (l < n) continue;
          double area = area_of(a - b, c - b);
          if (max_area < area) {
            max_area = area;
            p1 = 'A' + i;
            p2 = 'A' + j;
            p3 = 'A' + k;
          }
        }
      }
    }
    printf("%c%c%c\n", p1, p2, p3);
  }
  return 0;
}