2013年8月21日

UVa 143 - Orchard Trees

#include <cstdio>
#include <cmath>
 
inline double area(double x1, double y1, double x2, double y2, double x3, double y3) {
  return fabs(0.5 * ((y3 - y1) * (x2 - x1) - (y2 - y1) * (x3 - x1)));
}
 
inline double min(double a, double b) {
  return a < b ? a : b;
}
 
inline double max(double a, double b) {
  return a > b ? a : b;
}
 
int main() {
  char t;
  int n = 0;
  double x1, x2, x3, y1, y2, y3;
  while (scanf("%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3) && x1 || x2 || x3 || y1 || y2 || y3) {
    int xS = ceil(min(min(x1, x2), x3)), xE = max(max(x1, x2), x3);
    int yS = ceil(min(min(y1, y2), y3)), yE = max(max(y1, y2), y3);
    double x, y, a, a1, a2, a3;
    a = area(x1, y1, x2, y2, x3, y3);
    int ans = 0;
    if (xE > 99) xE = 99;
    if (yE > 99) yE = 99;
    if (!xS) xS = 1;
    if (!yS) yS = 1;
    for (x = xS; x <= xE; x++)
      for (y = yS; y <= yE; y++) {
        a1 = area(x1, y1, x2, y2, x, y);
        a2 = area(x1, y1, x, y, x3, y3);
        a3 = area(x, y, x2, y2, x3, y3);
        if ((fabs(a - (a1 + a2 + a3)) <= 1e-7)) ans++;
      }
    printf("%4d\n", ans);
  }
  return 0;
}

沒有留言:

張貼留言