2013年8月30日

UVa 109 - SCUD Busters

Reference : http://www.csie.ntnu.edu.tw/~u91029/ConvexHull.html#6
#include <cstdio>
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;

struct P {
  bool operator<(const P & other) const {
    return (x == other.x) ? (y < other.y) : (x < other.x);
  }
  int x, y;
};

typedef vector<P> Kingdom;

int cross(P o, P a, P b) {
  return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

Kingdom convexHull(Kingdom & k) {
  sort(k.begin(), k.end());
  P CH[100];
  int m = 0;
  for (int i = 0; i < k.size(); i++) {
    while (m >= 2 && cross(CH[m - 2], CH[m - 1], k[i]) <= 0) {
      m--;
    }
    CH[m++] = k[i];
  }
  for (int i = k.size() - 2, t = m + 1; i >= 0; i--) {
    while (m >= t && cross(CH[m - 2], CH[m - 1], k[i]) <= 0) {
      m--;
    }
    CH[m++] = k[i];
  }
  return Kingdom(CH, CH + m);
}

int area(Kingdom & k) {
  int sum = 0;
  for(int i = 1; i < k.size(); i++) {
    sum += (k[i - 1].x * k[i].y) - (k[i].x * k[i - 1].y);
  }
  return sum;
}

bool in(P p, Kingdom & k) {
  int sum = area(k);
  for (int i = 1; i < k.size() && sum >= 0; i++) {
    Kingdom temp;
    temp.PB(p);
    temp.PB(k[i - 1]);
    temp.PB(k[i]);
    temp.PB(p);
    int tempSum = area(temp);
    if (tempSum < 0) {
      return false;
    }
    sum -= tempSum;
  }
  return sum == 0;
}

int main() {
  vector<Kingdom> v;
  int n, x, y;
  while (scanf("%d", &n) && n != -1) {
    Kingdom k;
    for (int i = 0; i < n; i++) {
      scanf("%d%d", &x, &y);
      k.PB((P){x, y});
    }
    v.PB(convexHull(k));
  }
  vector<bool> over(v.size(), false);
  while (scanf("%d%d", &x, &y) == 2) {
    for (int i = 0; i < v.size(); i++) {
      if (!over[i]) {
        over[i] = in((P){x, y}, v[i]);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < v.size(); i++) {
    if (over[i]) {
      ans += area(v[i]);
    }
  }
  printf("%.2lf\n", ans * 0.5);
  return 0;
}

沒有留言:

張貼留言