POJ 1264 构建凸包判定点求面积(二)
intf("%d\n",a) #define f(i,a,n) for(i=a;i
eps);} inline double sqr(const double &x){ return x * x;} inline int gcd(int a, int b){ return !b a: gcd(b, a % b);} struct Point { double x, y; Point(const double &x = 0, const double &y = 0):x(x), y(y){} Point operator -(const Point &a)const{ return Point(x - a.x, y - a.y);} Point operator +(const Point &a)const{ return Point(x + a.x, y + a.y);} Point operator *(const double &a)const{ return Point(x * a, y * a);} Point operator /(const double &a)const{ return Point(x / a, y / a);} bool operator < (const Point &a)const{ return sgn(x - a.x) < 0 || (sgn(x - a.x) == 0 && sgn(y - a.y) < 0);} bool operator == (const Point &a)const{ return sgn(sgn(x - a.x) == 0 && sgn(y - a.y) == 0);} friend double det(const Point &a, const Point &b){ return a.x * b.y - a.y * b.x;} friend double dot(const Point &a, const Point &b){ return a.x * b.x + a.y * b.y;} friend double dist(const Point &a, const Point &b){ return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));} void in(){ scanf("%lf %lf", &x, &y); } void out()const{ printf("%lf %lf\n", x, y); } }; struct Poly //多边形类 { //vector
a; vector
p; //顺时针凸包 vector
tb;// 逆时针凸包 void in(const int &r) { p.resize(r); //不早凸包的时候可以把p改为a for(int i = 0; i < r; i++) p[i].in(); } //计算多边形的面积 double getArea() { int n = tb.size(); //平常的多边形就把tb换成a double ans=0; for(int i = 0; i < n; i++) ans += det(tb[i], tb[(i + 1)%n]); return ans / 2; } //判断点集是否为凸包(返回m-1==n),或者用凸包点算出凸包顶点tb(本题即是) void isCanHull() { sort(p.begin(), p.end()); p.erase(unique(p.begin(), p.end()), p.end()); int n = p.size(); tb.resize(n * 2 + 5); int m = 0; for(int i = 0; i < n; i++) { while(m >
1 && sgn(det(tb[m - 1] - tb[m - 2], p[i] - tb[m - 2])) <= 0)m--; tb[m++] = p[i]; } int k = m; for(int i = n - 2; i >= 0; i--) { while(m > k && sgn(det(tb[m - 1] - tb[m -2], p[i] - tb[m - 2])) <= 0)m--; tb[m++] = p[i]; } tb.resize(m); if(m > 1)tb.resize(m - 1); //for(int i = 0; i < m - 1; i++) tb[i].out(); } //判断点t(圆心)是否在凸包内部，这个是O(logn)的算法 int isContainOlogn(const Point &t) { int n = tb.size(); if(n < 3) return 0; Point g = (tb[0] + tb[n / 3] + tb[n * 2 / 3] )/ 3.0; int l = 0, r = n; while(l + 1 < r) { int mid = (l + r) >> 1; int k = sgn(det(tb[l] - g, tb[mid] - g) ); int dl = sgn(det(tb[l] - g, t - g) ); int dr = sgn(det(tb[mid] - g, t - g) ); if(k > 0) { if(dl >= 0 && dr < 0) r = mid; else l = mid; } else { if(dl < 0 && dr >= 0) l = mid; else r = mid; } } r %= n; int res = sgn(det(tb[l] - t, tb[r] - t)); if(res >= 0) return 1; return 0; } }poly[MM]; double sum=0,a,b; int n,i,k=0,vis[MM]; int main() { while(sca(n)&&n!=-1) { poly[k].in(n); poly[k++].isCanHull(); } while(~scanf("%lf%lf",&a,&b)) { Point bb(a,b); for(i=0;i