首页 > ACM题库 > HDU-杭电 > HDU 3814-Signal Coverage-计算几何-[解题报告]HOJ
2015
04-13

HDU 3814-Signal Coverage-计算几何-[解题报告]HOJ

Signal Coverage

问题描述 :

GSM, Global System for Mobile Communications, is the world’s most popular standard for mobile telephone systems. CMCC, China Mobile Communications Corporation, has almost 500,000 GSM base stations, but some cellphone users still complain about the signal coverage problem. Because of building block or some other reasons, we can assume that a base station covers an area of a simple polygon, and they don’t intersect with each other. We have a map that contains some simple polygons which represents the coverage of base stations. For the coverage ratio statistics, we drew a segment on the map, and we consider the C/L be the coverage ratio. C is the length of segment to be covered; L is the length of the segment we drew.
Please notice that, if a part of the segment can be considered as covered, that part must be inside or on the boundary of the polygon.

输入:

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with two coordinate, indicating the start and the end of the segment we drew. Then followed an integer, N, indicating there are N simple polygons. Each polygon starts with an integer, C, and C coordinates followed.

Technical Specification

1. 1 <= T <= 20
2. The number of all the points on the map is less than 100,000.
3. The coordinate of all the points consists of integers, and the value is in the range of [-100000, 100000]

输出:

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with two coordinate, indicating the start and the end of the segment we drew. Then followed an integer, N, indicating there are N simple polygons. Each polygon starts with an integer, C, and C coordinates followed.

Technical Specification

1. 1 <= T <= 20
2. The number of all the points on the map is less than 100,000.
3. The coordinate of all the points consists of integers, and the value is in the range of [-100000, 100000]

样例输入:

2

0 0 2 0
1
4 0 0 1 0 1 1 0 1

0 0 2 0
1
4 0 -1 1 -1 1 1 0 1

样例输出:

Case 1: 50.00%
Case 2: 50.00%

给一条直线和多个简单多边形,求在多边形内(包括边上)的线段长度占总长度的百分比。

 

WA了一晚上和一上午换了N种方法终于想到了个简单又好写不用各种讨论无视各种trick的方法。

核心思想就是把线段根据交点分成若干段,然后判断每段的某一边是否有面积。

那这个怎么判断呢?

Signal Coverage

如上图:不告诉你具体的多边形情况,只知道多边形的边与线段相交的情况,能判断出哪些是区域是多边形内,哪些是外面的么?

很简单的啦,交替就行了,如下图:

Signal Coverage

具体做法么就是把交点都求出来,并记录这个交点在线段的两边各产生了几条线(多边形的边的某个端点在线段上会在某一边产生一条线,普通的相交会在两边都产生线,重合的就无视掉吧),排个序,相同的点都合并起来。

求长度么就是扫一遍,看到目前这个点为止在线段的两边各已出现多少线,只要有一边是奇数个,那接下去的一段区域就在某个多边形内了。

那线段的起点是否在多边形内呢?反向延长到足够远处,从哪里开始一路判断过来就好了。

 

 

 

#include<iostream>
#include<algorithm>
#include<cmath>
#define eps 1e-9
using namespace std;
double f_abs(double x){
    return x<0?-x:x;
}
struct Point{
    double x,y;
    bool up,dn;
    void disp(){
        printf("%lf %lf\n",x,y);
    }
    void get(){
        scanf("%lf%lf",&x,&y);
    }
    bool friend operator<(Point a,Point b){
        if(f_abs(a.x-b.x)<eps)return a.y<b.y;
        return a.x<b.x;
    }
    bool friend operator>(Point a,Point b){
        return b<a;
    }
    bool friend operator==(Point a,Point b){
        return f_abs(a.x-b.x)<eps&&f_abs(a.y-b.y)<eps;
    }
};
struct Line{
    Point s,e;
    bool friend operator<(Line a,Line b){
        return a.s<b.s;
    }
    void st(){
        Point t;
        if(s>e){
            t=s;s=e;e=t;
        }
    }
    void get(){
        s.get();e.get();
        st();
    }
};
Line line[200000],myl[2];
Point ep[200000];
int en;
double get_cross(Point a,Line b){
    double ax,ay,bx,by;
    ax=b.s.x-a.x;
    ay=b.s.y-a.y;
    bx=b.e.x-a.x;
    by=b.e.y-a.y;
    return ax*by-ay*bx;
}
int inter(Line a,Line b,Point &rp=Point()){//0:不相交 1:相交 2、3:端点相交,a在b某一边 4:重合
    double cj[2];
    cj[0]=get_cross(b.s,a);cj[1]=get_cross(b.e,a);
    if(cj[0]*cj[1]>eps)return 0;
    cj[0]=get_cross(a.s,b);cj[1]=get_cross(a.e,b);
    if(cj[0]*cj[1]>eps)return 0;
    if(f_abs(cj[0])<eps&&f_abs(cj[1])<eps){
        return 4;
    }
    if(f_abs(cj[0])<eps){
        rp=a.s;
        if(cj[1]>eps)return 2;
        else return 3;
    }else if(f_abs(cj[1])<eps){
        rp=a.e;
        if(cj[0]>eps)return 2;
        else return 3;
    }else{
        double key1=(a.e.x-a.s.x)*(b.e.y-b.s.y);  
        double key2=(b.e.x-b.s.x)*(a.e.y-a.s.y);  
        double key=key1-key2;  
        rp.x=(a.s.y-b.s.y)*(a.e.x-a.s.x)*(b.e.x-b.s.x);  
        rp.x-=key2*a.s.x-key1*b.s.x;  
        rp.x/=key;  
        if(f_abs(b.e.x-b.s.x)<eps)rp.y=(a.e.y-a.s.y)/(a.e.x-a.s.x)*(rp.x-a.s.x)+a.s.y;  
        else rp.y=(b.e.y-b.s.y)/(b.e.x-b.s.x)*(rp.x-b.s.x)+b.s.y;  
        return 1;
    }
}
int ln;
void get_myl2(){
    double dy=myl[0].e.y-myl[0].s.y,dx=myl[0].e.x-myl[0].s.x;
    double t=sqrt(dy*dy+dx*dx);
    dy/=t;dx/=t;
    myl[1].e=myl[0].s;
    myl[1].s.x=myl[1].e.x-300000*dx;
    myl[1].s.y=myl[1].e.y-300000*dy;
}
void get_data(){
    myl[0].get();
    int t,n,i;
    int pcnt=0;
    Point p[2],ini;
    ln=0;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        ini.get();
        if(n==1)continue;
        p[0]=ini;
        bool f=0;
        for(i=1;i<n;i++){
            f^=1;
            p[f].get();
            line[ln].s=p[f^1];
            line[ln].e=p[f];
            line[ln++].st();
        }
        line[ln].s=p[f];
        line[ln].e=ini;
        line[ln++].st();
    }
    get_myl2();
}
double get_len(Point a,Point b){
    return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}
void get_ep(Line l){
    en=0;
    int t,i;
    for(i=0;i<ln;i++){
        t=inter(line[i],l,ep[en]);
        if(!t||t==4)continue;
        if(t==1){
            ep[en].up=1;
            ep[en++].dn=1;
        }else if(t==2){
            ep[en].up=1;
            ep[en++].dn=0;
        }else{
            ep[en].up=0;
            ep[en++].dn=1;
        }
    }
    sort(ep,ep+en);
    int ten=0;
    for(i=0;i<en;i++){
        if(ten&&ep[i]==ep[ten-1]){
            ep[ten-1].up^=ep[i].up;
            ep[ten-1].dn^=ep[i].dn;
        }else ep[ten++]=ep[i];
    }
    en=ten;
}
void run(){
    if(myl[0].s==myl[0].e){
        printf("0.00%%\n");
        return;
    }
    int i;
    bool in=0,left=0,right=0;
    get_ep(myl[1]);
    for(i=0;i<en;i++){
		left^=ep[i].up;
		right^=ep[i].dn;
    }
	if(left||right)in=1;
	else in=0;
    get_ep(myl[0]);
    double len=get_len(myl[0].s,myl[0].e),res=0;
    Point lp=myl[0].s;
    ep[en++]=myl[0].e;
    for(i=0;i<en;i++){
        if(ep[i]==myl[0].s)continue;
        if(in)res+=get_len(ep[i],lp);
		left^=ep[i].up;
		right^=ep[i].dn;
        if(left||right)in=1;
		else in=0;
        lp=ep[i];
    }
    printf("%.2lf%%\n",res*100/len);
}
int main(){
    int i,t;
    scanf("%d",&t);
    for(i=1;i<=t;i++){
        get_data();
        printf("Case %d: ",i);
        run();
    }
    return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/he11oworld/article/details/6903471


  1. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  2. [email protected]

  3. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  4. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。