#include #include #include #include #include #include #include using namespace std; #define EPSILON (1e-7) class point { public: int x, y; point(); point(int &_x, int &_y); point(const point &_p); }; point::point(int &_x, int &_y){ x = _x; y = _y; } point::point(const point &_p) { x = _p.x; y = _p.y; } bool operator<(const pair &x, const pair &y) { if (x.second == INT_MAX && y.second == INT_MAX) { return (x.first < y.first); } if (x.second == INT_MAX) { return (x.first <= y.first); } if (y.second == INT_MAX) { return (x.second < y.first); } if (x.second < y.second) return true; if (x.second > y.second) return false; if (x.first < y.first ) return true; if (x.first > y.first ) return false; return false; } deque< pair > online[4100]; /* Calculate intersection point between line-segment(p1 - p2) & line(y = Y) */ double cross(point p1, point p2, int Y) { return ((double)(p2.x - p1.x) / (double)(p2.y - p1.y)) * (double)(Y - p2.y) + (double)p2.x; } int main() { int n, x, y, miny, maxy; deque p; // ifstream cin("area.txt"); while (1) { p.clear(); for (int i = 0; i < 4100; i++) { online[i].clear(); } cin >> n; if (n == 0) { break; } miny = 2010; maxy = -2010; for (int i = 0; i < n; i++) { cin >> x >> y; if (miny > y) { miny = y; } if (maxy < y) { maxy = y; } p.push_back(point(x, y)); } p.push_back(p.front()); // Trace line for (deque::iterator i = p.begin(); i+1 != p.end(); i++) { deque::iterator j = i+1; for (int y = (i->y < j->y ? i->y : j->y); y < (i->y > j->y ? i->y : j->y); y++) { double dx1 = cross(*i, *j, y); double dx2 = cross(*i, *j, y+1); if (fabs(dx2 - dx1) < EPSILON) { online[y+2050].push_back(make_pair((int)floor(dx1), INT_MAX)); } else { if (dx1 > dx2) { double tmp = dx1; dx1 = dx2; dx2 = tmp; } int x1 = (int)floor(dx1); int x2 = (dx2 - floor(dx2) < EPSILON ? (int)floor(dx2)-1 : (int)floor(dx2)); online[y+2050].push_back(make_pair(x1, x2)); } } } for (int y = miny-1; y <= maxy+1; y++) { sort(online[y+2050].begin(), online[y+2050].end()); for (deque< pair >::iterator i = online[y+2050].begin(); i != online[y+2050].end(); i +=2 ) { deque< pair >::iterator j = i+1; /* cout << "(" << i->first << "," << i->second << ")-"; cout << "(" << j->first << "," << j->second << ") "; */ if (i->second == INT_MAX) { i->second = i->first; } if (j->second == INT_MAX) { j->first--; j->second = j->first; } } /* cout << endl; */ } unsigned int area = 0; for (int y = miny-1; y <= maxy+1; y++) { for (deque< pair >::iterator i = online[y+2050].begin(); i != online[y+2050].end(); i +=2 ) { deque< pair >::iterator j = i+1; /* cout << "(" << i->first << "," << i->second << ")-"; cout << "(" << j->first << "," << j->second << ") "; */ if (i != online[y+2050].begin() && (j-2)->second >= i->first) { area += j->second - (j-2)->second; } else { area += j->second - i->first + 1; } } /* cout << endl; */ } cout << area << endl; } return 0; }