首页 > ACM题库 > HDU-杭电 > HDU 2892-area-计算几何-[解题报告]HOJ
2014
02-17

HDU 2892-area-计算几何-[解题报告]HOJ

area

问题描述 :

小白最近被空军特招为飞行员,参与一项实战演习。演习的内容是轰炸某个岛屿。。。
作为一名优秀的飞行员,任务是必须要完成的,当然,凭借小白出色的操作,顺利地将炸弹投到了岛上某个位置,可是长官更关心的是,小白投掷的炸弹到底摧毁了岛上多大的区域?
岛是一个不规则的多边形,而炸弹的爆炸半径为R。
小白只知道自己在(x,y,h)的空间坐标处以(x1,y1,0)的速度水平飞行时投下的炸弹,请你计算出小白所摧毁的岛屿的面积有多大. 重力加速度G = 10.

输入:

首先输入三个数代表小白投弹的坐标(x,y,h);
然后输入两个数代表飞机当前的速度(x1, y1);
接着输入炸弹的爆炸半径R;
再输入一个数n,代表岛屿由n个点组成;
最后输入n行,每行输入一个(x’,y’)坐标,代表岛屿的顶点(按顺势针或者逆时针给出)。(3<= n < 100000)

输出:

首先输入三个数代表小白投弹的坐标(x,y,h);
然后输入两个数代表飞机当前的速度(x1, y1);
接着输入炸弹的爆炸半径R;
再输入一个数n,代表岛屿由n个点组成;
最后输入n行,每行输入一个(x’,y’)坐标,代表岛屿的顶点(按顺势针或者逆时针给出)。(3<= n < 100000)

样例输入:

0 0 2000
100 0
100 

4
1900 100
2000 100
2000 -100
1900 -100

样例输出:

15707.96

以圆心为中心将简单多边形划分为n个矢量三角形,对每个三角形与圆求交,根据有向边判断相交面积正负,最后相加取绝对值。

一个顶点在圆心的三角形与圆的交需要讨论的情况比较少,容易计算。

#include<stdio.h>
 #include<string.h>
 #include<stdlib.h>
 #include<math.h>
 #include<algorithm>
 const int maxn = 111111;
 const int maxisn = 21;
 const double eps = 1e-8;
 const double pi = acos(-1.0);
 int dcmp(double x)
 {
     if(x > eps) return 1;
     return x < -eps ? -1 : 0;
 }
 struct Point
 {
     double x, y;
     Point(){x = y = 0;}
     Point(double a, double b)
     {x = a, y = b;}
     inline Point operator-(const Point &b)const
     {return Point(x - b.x, y - b.y);}
     inline Point operator+(const Point &b)const
     {return Point(x + b.x, y + b.y);}
     inline Point operator*(const double &b)const
     {return Point(x * b, y * b);}
     inline double dot(const Point &b)const
     {return x * b.x + y * b.y;}
     inline double cross(const Point &b, const Point &c)const
     {return (b.x - x) * (c.y - y) - (c.x - x) * (b.y - y);}
     inline double Dis(const Point &b)const
     {return sqrt((*this - b).dot(*this - b));}
     inline bool InLine(const Point &b, const Point &c)const//三点共线
     {return !dcmp(cross(b, c));}
     inline bool OnSeg(const Point &b, const Point &c)const//点在线段上,包括端点
     {return InLine(b, c) && (*this - c).dot(*this - b) < eps;}
 };
 inline double min(double a, double b)
 {return a < b ? a : b;}
 inline double max(double a, double b)
 {return a > b ? a : b;}
 inline double Sqr(double x)
 {return x * x;}
 inline double Sqr(const Point &p)
 {return p.dot(p);}
 Point LineCross(const Point &a, const Point &b, const Point &c, const Point &d)
 {
     double u = a.cross(b, c), v = b.cross(a, d);
     return Point((c.x * v + d.x * u) / (u + v), (c.y * v + d.y * u) / (u + v));
 }
 double LineCrossCircle(const Point &a, const Point &b, const Point &r, 
             double R, Point &p1, Point &p2)
 {
     Point fp = LineCross(r, Point(r.x + a.y - b.y, r.y + b.x - a.x), a, b);
     double rtol = r.Dis(fp);
     double rtos = fp.OnSeg(a, b) ? rtol : min(r.Dis(a), r.Dis(b));
     double atob = a.Dis(b);
     double fptoe = sqrt(R * R - rtol * rtol) / atob;
     if(rtos > R - eps) return rtos;
     p1 = fp + (a - b) * fptoe;
     p2 = fp + (b - a) * fptoe;
     return rtos;
 }
 double SectorArea(const Point &r, const Point &a, const Point &b, double R)
 //不大于180度扇形面积,r->a->b逆时针
 {
     double A2 = Sqr(r - a), B2 = Sqr(r - b), C2 = Sqr(a - b);
     return R * R * acos((A2 + B2 - C2) * 0.5 / sqrt(A2) / sqrt(B2)) * 0.5;
 }
 double TACIA(const Point &r, const Point &a, const Point &b, double R)
 //TriangleAndCircleIntersectArea,逆时针,r为圆心
 {
     double adis = r.Dis(a), bdis = r.Dis(b);
     if(adis < R + eps && bdis < R + eps) return r.cross(a, b) * 0.5;
     Point ta, tb;
     if(r.InLine(a, b)) return 0.0;
     double rtos = LineCrossCircle(a, b, r, R, ta, tb);
     if(rtos > R - eps) return SectorArea(r, a, b, R);
     if(adis < R + eps) return r.cross(a, tb) * 0.5 + SectorArea(r, tb, b, R);
     if(bdis < R + eps) return r.cross(ta, b) * 0.5 + SectorArea(r, a, ta, R);
     return r.cross(ta, tb) * 0.5 + 
         SectorArea(r, a, ta, R) + SectorArea(r, tb, b, R);
 }
 double SPICA(int n, Point r, double R)//SimplePolygonIntersectCircleArea
 {
     int i;
     Point ori, p[2];
     scanf("%lf%lf", &ori.x, &ori.y);
     p[0] = ori;
     double res = 0, if_clock_t;
     for(i = 1; i <= n; ++ i)
     {
         if(i == n) p[i & 1] = ori;
         else scanf("%lf%lf", &p[i & 1].x, &p[i & 1].y);
         if_clock_t = dcmp(r.cross(p[~i & 1], p[i & 1]));
         if(if_clock_t < 0) res -= TACIA(r, p[i & 1], p[~i & 1], R);
         else res += TACIA(r, p[~i & 1], p[i & 1], R);
     }
     return fabs(res);
 }
 Point boom;
 int n;
 double R;
 int main()
 {
     double sx, sy, h, vx, vy;
     while(scanf("%lf%lf%lf", &sx, &sy, &h) != EOF)
     {
         scanf("%lf%lf%lf", &vx, &vy, &R);
         h = sqrt(2 * h / 10);
         boom = Point(h * vx + sx, h * vy + sy);
         scanf("%d", &n);
         printf("%.2f\n", SPICA(n, boom, R));
     }
     return 0;
 }

解题参考:http://www.cnblogs.com/CSGrandeur/archive/2012/09/08/2677124.html


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。