Area of Polygons
2007.08.23 12:50 ACM/ICPC 2003
[問題] 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 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |