Area of Polygons

[問題] ACM/ICPC Asia Regional 2003 Aizu: Problem C

[解説]

プログラム・プロムナードを参考。
詳細は後日。

[サンプルプログラム]

001 #include<iostream>
002 #include<algorithm>
003 #include<vector>
004 #include<cassert>
005 #include<cmath>
006 using namespace std;
007 
008 #define MAX 100
009 #define SHIFT 2000
010 #define EPS 0.00000001
011 
012 class Point{
013     public:
014     double x, y;
015     Point(){}
016     Point(int x, int y):x(x), y(y){}
017 };
018 
019 class Segment{
020     public:
021     int left, right;
022     Segment(){}
023     Segment( int left, int right ): left(left), right(right){}
024     
025     bool operator < ( const Segment &s ) const{
026         if ( left == s.left ) return right < s.right;
027         else return left < s.left;
028     }
029 };
030 
031 int n;
032 Point P[MAX+1];
033 int minY, maxY;
034 
035 double getX( Point p1, Point p2, int y ){
036     assert( p1.y != p2.y );
037     return 1.0*(p2.x - p1.x)*(y - p1.y)/(p2.y - p1.y) + p1.x;
038 }
039 
040 void compute(){
041     int total = 0;
042     
043     for ( int y = minY; y <= maxY - 1; y++ ){
044         vector<Segment> targets;
045         for ( int i = 0; i < n; i++ ){
046             if ( P[i].y <= y && P[i+1].y <= y ||
047             P[i].y >= y+1 && P[i+1].y >= y+1 ) continue;
048             double x1, x2;
049             int left, right;
050             x1 = getX(P[i], P[i+1], y);
051             x2 = getX(P[i], P[i+1], y+1);
052             left = (int)(min( x1, x2 ));
053             right = (int)(max( x1, x2 ) + 1 - EPS);
054             targets.push_back( Segment( left, right ) );
055         }
056         
057         assert( targets.size() % 2 == 0 );
058         sort ( targets.begin(), targets.end() );
059         
060         int prev = 0;
061         for ( int i = 0; i < targets.size(); i += 2 ){
062             total += targets[i+1].right - max( targets[i].left, prev );
063             prev = targets[i+1].right;
064         }
065     }
066     
067     cout << total << endl;
068 }
069 
070 bool input(){
071     cin >> n;
072     if ( n == 0 ) return false;
073     int x, y;
074     minY = 2001;
075     maxY = -2001;
076     
077     for ( int i = 0; i < n; i++ ){
078         cin >> x >> y;
079         x += SHIFT; y += SHIFT;
080         minY = min( minY, y );
081         maxY = max( maxY, y );
082         P[i] = Point(x, y);
083     }
084     P[n] = P[0];
085     
086     return true;
087 }
088 
089 main(){
090     while( input() ) compute();
091 }