HDU 5130（计算几何+圆与多边形相交)

红太狼 2022-06-09 12:19 203阅读 0赞

问题描述:

Two countries A-Land and B-Land are at war. The territory of A-Land is a simple polygon with no more than 500 vertices. For military use, A-Land constructed a radio tower (also written as A), and it's so powerful that the whole country was under its signal. To interfere A-Land's communication, B-Land decided to build another radio tower (also written as B). According to an accurate estimation, for any point P, if the euclidean distance between P and B is no more than k (0.2 ≤ k < 0.8) times of the distance between P and A, then point P is not able to receive clear signals from A, i.e. be interfered. Your task is to calculate the area in A-Land's territory that are under B-Land's interference.

Input

There are no more than 100 test cases in the input.   
  
In each test case, firstly you are given a positive integer N indicating the amount of vertices on A-Land's territory, and an above mentioned real number k, which is rounded to 4 digits after the decimal point.   
  
Then N lines follow. Each line contains two integers x and y (|x|, |y| ≤ 1000), indicating a vertex's coordinate on A's territory, in counterclockwise or clockwise order.   
  
The last two lines of a test case give radio tower A and B's coordinates in the same form as vertexes' coordinates. You can assume that A is not equal to B.

Output

For each test case, firstly output the case number, then output your answer in one line following the format shown in sample. Please note that there is a blank after the ':'.   
  
Your solution will be accepted if its absolute error or relative error is no more than 10-6.   
  
This problem is special judged.

Sample Input

4 0.5000
    -1 -1
    1 -1
    1 1
    -1 1
    0 0
    -1 0

Sample Output

Case 1: 0.2729710441

题目题意:题目给我们一个多边形的n个顶点，一个比值k,和俩个发射台的坐标point A和point B，问我们在那个多边形内，有多少的面积被B发射台干扰。（某点能被发射台B干扰的条件是：这个点到发射台B的距离小于等于K 倍到发射台A的距离。

题目分析:我们来找临界点恰好可以干扰的点p(x,y) 可以列出方程(dis表示距离)

dis(B,p)==k dis(A,p) 化简一下是一个圆的方程（结果比较复杂，耐心一点！）

圆的内部的点肯定是要被干扰的，就变成了多边形和圆相交求面积了（模板)

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    using namespace std;
    
    const int MAX = 520;
    const double pi = acos(-1.0);
    struct point {
    	double x, y;
    };
    point p[MAX];//多边形点的信息
    point c;//圆的坐标
    double r;//保存圆的半径
    const double eps = 1e-8;
    int dcmp(double x) {
    	return x < -eps ? -1 : x > eps ? 1 : 0;
    }
    double disp2p(point a,point b)
    {
    	return sqrt( ( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y ) );
    }
    double crossProduct(point a,point b,point c)
    {
    	return (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y);
    }
    point l2l_inst_p(point u1,point u2,point v1,point v2)
    {
    	point ans = u1;
    	double t = ((u1.x - v1.x)*(v1.y - v2.y) - (u1.y - v1.y)*(v1.x - v2.x))/
    				((u1.x - u2.x)*(v1.y - v2.y) - (u1.y - u2.y)*(v1.x - v2.x));
    	ans.x += (u2.x - u1.x)*t;
    	ans.y += (u2.y - u1.y)*t;
    	return ans;
    }
    int l2c_inst_p(point c,double r,point l1,point l2,point *pv)
    {
    	int cnt = 0;
    	double d = fabs( crossProduct(c,l1,l2) )/disp2p(l1,l2);
    	if( dcmp(d-r) > 0 )
    		return 0;
    	point p = c;
    	double t;
    	p.x += l1.y - l2.y;
    	p.y += l2.x - l1.x;
    	p = l2l_inst_p(p,c,l1,l2);
    	t = sqrt(r*r - disp2p(p,c)*disp2p(p,c))/disp2p(l1,l2);
    	pv[cnt].x = p.x + (l2.x - l1.x)*t;
    	pv[cnt++].y = p.y + (l2.y - l1.y)*t;
    	if( dcmp(d-r) == 0 )
    		return cnt;
    	pv[cnt].x = p.x - (l2.x - l1.x)*t;
    	pv[cnt++].y = p.y - (l2.y - l1.y)*t;
    	return cnt;
    }
    bool onSegment(point a, point b, point c)
    {
    	if( dcmp(c.x - a.x) == 0 && dcmp(c.y - a.y) == 0 || dcmp(c.x - b.x) == 0 && dcmp(c.y - b.y) == 0 )
    		return false;
    	if( dcmp(crossProduct(a,b,c)) == 0 && dcmp(c.x - min(a.x,b.x)) >= 0 &&
    		dcmp(c.x-max(a.x,b.x)) <= 0 && dcmp(c.y - min(a.y,b.y)) >= 0 && dcmp(c.y-max(a.y,b.y)) <= 0 )
    		return true;
    	return false;
    }
    int seg2c_inst_p(point c,double r,point l1,point l2,point *p)
    {
    	point pv[3];
    	int cnt = l2c_inst_p(c, r, l1, l2, pv);
    	int cntp = 0;
    	for (int i=0;i<cnt;i++)
    		if( onSegment(l1, l2, pv[i]) )
    			p[cntp++] = pv[i];
    	if(	cntp == 2 ) {
    		if(disp2p(p[0], l1) > disp2p(p[1], l1) )
    			swap(p[0], p[1]);
    	}
    	return cntp;
    }
    double area_triangle(point a,point b,point c)
    {
    	return fabs( crossProduct(a,b,c) )/2.0;
    }
    double area_shan(point a, point b, point c, double r) {
    	double aa = disp2p(c, b);
    	double bb = disp2p(a, c);
    	double cc = disp2p(a, b);
    	double ang = acos((aa*aa + bb*bb - cc*cc)/(2*aa*bb));
    	return ang/2*r*r;
    }
    //三角形与圆的交面积，其中c是圆心
    double area_triangle2circle(point a, point b, point c, double r) {
    	point p[3];
    	int cnt = seg2c_inst_p(c, r, a, b, p);
    	if( dcmp(crossProduct(a, b, c)) == 0 )
    		return 0;
    	if( cnt == 0 ) {
    		if( dcmp(disp2p(a, c) - r) <= 0 && dcmp(disp2p(b, c) - r) <= 0 )
    			return area_triangle(a, b, c);
    		else
    			return area_shan(a, b, c, r);
    	}
    	if( cnt == 1 ) {
    		if( dcmp(disp2p(a, c) - r) > 0 && dcmp(disp2p(b, c) - r) > 0 )
    			return area_shan(a, b, c, r);
    		if( dcmp(disp2p(a, c) - r) > 0 )
    			swap(a, b);
    		return area_shan(p[0], b, c, r) + area_triangle(a, p[0], c);
    	}
    	if( cnt == 2 ) {
    		return area_shan(a, p[0], c, r) + area_shan(p[1], b, c, r)
    				+ area_triangle(p[0], p[1], c);
    	}
    }
    double solve(int n) {//返回值
    	double area = 0;
    	for (int i=0;i<n;i++) {
    		area += area_triangle2circle(p[i], p[(i+1)%n], c, r) *
    				 dcmp(crossProduct(c, p[(i+1)%n], p[i]));
    	}
    	return fabs(area);
    }
    int main()
    {
        int n,icase=1;
        double k;
        while (scanf("%d%lf",&n,&k)!=EOF) {
            for (int i=0;i<n;i++)
                scanf("%lf%lf",&p[i].x,&p[i].y);
            struct point A,B;
            scanf("%lf%lf",&A.x,&A.y);
            scanf("%lf%lf",&B.x,&B.y);
            k=k*k;
            c.x=(B.x-k*A.x)/(1-k);
            c.y=(B.y-k*A.y)/(1-k);
            double a=(k*A.x*A.x-B.x*B.x)/(1-k);
            double b=pow((k*A.x-B.x)/(1-k),2);
            double c=(k*A.y*A.y-B.y*B.y)/(1-k);
            double d=pow((k*A.y-B.y)/(1-k),2);
            r=sqrt(a+b+c+d);
            double ans=solve(n);
            printf("Case %d: %.10lf\n",icase++,ans);
        }
        return 0;
    }