POJ 2574 - Saskatchewan

http://poj.org/problem?id=2574

概要

\(N\) 個の格子点が与えられる。 これを順に繋いだ多角形の中に 1 x 1 のマスがいくつあるか答える。

制約

解法

まず \(N\) 本の線分を y 座標に関して昇順にソートしておく。

各 x 座標 x0 について、直線 x = x0 との交点を調べていき、同様に直線 x = x0 + 1 の交点も調べ、多角形の内部の領域に関して共通部分の大きさを調べて正方形を数える。 このとき、y 軸に平行な線分の扱いや、線分の端点が x0, x0 + 1 に一致するような線分の扱いに注意する。

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <complex>
  4 #include <cmath>
  5 using namespace std;
  6 typedef complex<int> PL;
  7 typedef complex<double> P;
  8 
  9 inline long long ABS(long long x) { return x < 0 ? -x : x; }
 10 inline long long cross(const PL& a, const PL& b) { return static_cast<long long>(a.real())*b.imag() - static_cast<long long>(b.real())*a.imag(); }
 11 
 12 struct line/*{{{*/
 13 {
 14   PL a, b;
 15   line() {}
 16   line(const PL& p, const PL& q) : a(p), b(q) {}
 17 };/*}}}*/
 18 
 19 struct segment/*{{{*/
 20 {
 21   PL a, b;
 22   PL pa, pb;
 23   segment() {}
 24   segment(const PL& x, const PL& y) : a(x), b(y) {}
 25 
 26   inline int intersects(const line& ln) const
 27   {
 28     long long x = cross(ln.b - ln.a, a - ln.a);
 29     long long y = cross(ln.b - ln.a, b - ln.a);
 30     if (x == 0 && y == 0) {
 31       return 0;
 32     } else if (x == 0) {
 33       return 1;
 34     } else if (y == 0) {
 35       return 2;
 36     } else if ((x/ABS(x)) * (y/ABS(y)) < 0) {
 37       return 3;
 38     } else {
 39       return 4;
 40     }
 41   }
 42 
 43   inline P intersection(const line& ln) const
 44   {
 45     // assert(intersects(ln))
 46     const PL x = b - a;
 47     const PL y = ln.b - ln.a;
 48     const P xx(x.real(), x.imag());
 49     const P aa(a.real(), a.imag());
 50     return aa + xx*double(cross(y, ln.a - a))/double(cross(y, x));
 51   }
 52 };/*}}}*/
 53 
 54 struct by_y
 55 {
 56   bool operator()(const segment& l, const segment& r) const
 57   {
 58     int a = min(l.a.imag(), l.b.imag());
 59     int b = min(r.a.imag(), r.b.imag());
 60     if (a == b) {
 61       return max(l.a.imag(), l.b.imag()) < max(r.a.imag(), r.b.imag());
 62     } else {
 63       return a < b;
 64     }
 65   }
 66 };
 67 
 68 int main()
 69 {
 70   static PL polygon[100];
 71   int left = 1000000, right = 0;
 72   int N = 0;
 73   for (int x, y; scanf("%d %d", &x, &y) != EOF;) {
 74     polygon[N++] = PL(x, y);
 75     left = min(left, x);
 76     right = max(right, x);
 77   }
 78   static segment ss[100];
 79   for (int i = 0; i < N; i++) {
 80     ss[i].a = polygon[i];
 81     ss[i].b = polygon[(i+1)%N];
 82   }
 83   for (int i = 0; i < N; i++) {
 84     ss[i].pa = ss[(i-1+N)%N].a;
 85     ss[i].pb = ss[(i-1+N)%N].a;
 86   }
 87   sort(ss, ss+N, by_y());
 88 
 89   long long ans = 0;
 90   static int ys[2][100];
 91   int M[2] = {0, 0};
 92   for (int x = left, cnt = 0; x <= right; x++, cnt ^= 1) {
 93     const line ln(PL(x, -2), PL(x, -1));
 94     int *p = ys[cnt];
 95     int& n = M[cnt];
 96     n = 0;
 97     for (int i = 0; i < N; i++) {
 98       switch (ss[i].intersects(ln)) {
 99         case 0:
100           {
101             if (n % 2 == 1) {
102               int y1 = ss[i].a.imag(), y2 = ss[i].b.imag();
103               if (y1 > y2) {
104                 swap(y1, y2);
105               }
106               p[n++] = y1;
107               p[n++] = y1;
108               p[n++] = y2;
109             } else {
110               int r = segment(ss[i].b, ss[i].pa).intersects(line(ln));
111               if (r != 4) {
112                 p[n++] = ss[i].a.imag();
113               }
114             }
115           }
116           break;
117         case 1:
118           {
119             int r = segment(ss[i].b, ss[i].pa).intersects(line(ln));
120             if (r != 4) {
121               p[n++] = ss[i].a.imag();
122             }
123           }
124           break;
125         case 2:
126           break;
127         case 3:
128           {
129             double y = ss[i].intersection(ln).imag();
130             if (n % 2 == 0) {
131               p[n++] = ceil(y);
132             } else {
133               p[n++] = floor(y);
134             }
135           }
136           break;
137         case 4:
138           break;
139       }
140     }
141     const int *q = ys[cnt ^ 1];
142     const int m = M[cnt ^ 1];
143     for (int i = 0, j = 0; i < n && j < m;) {
144       int beg1 = p[i], end1 = p[i+1];
145       int beg2 = q[j], end2 = q[j+1];
146       if (end1 <= beg2) {
147         i += 2;
148       } else if (end2 <= beg1) {
149         j += 2;
150       } else if (end1 <= end2) {
151         ans += static_cast<long long>(end1 - max(beg1, beg2));
152         i += 2;
153       } else {
154         ans += static_cast<long long>(end2 - max(beg1, beg2));
155         j += 2;
156       }
157     }
158   }
159   printf("%lld\n", ans);
160   return 0;
161 }
poj/2574.cc