首页 > ACM题库 > HDU-杭电 > HDU 1154 Cutting a Polygon-计算几何-[解题报告] C++
2013
12-03

HDU 1154 Cutting a Polygon-计算几何-[解题报告] C++

Cutting a Polygon

问题描述 :

Given is a simple but not necessarily convex polygon. Given is also a line in the plane. If the polygon is cut along the line then we may get several smaller polygons. Your task is to find the length of the cut, that is the total length of the segments in the intersection of the line and the polygon.

输入:

Input consists of a number of cases. The data of each case appears on a number of input lines, the first of which contains two non negative integers n and m giving the number of the vertices of the polygon and the number of cutting lines to consider, 3 ≤ n ≤ 1000. The following n lines contain coordinates of the vertices of the polygon; each line contains the x and y coordinates of a vertex. The vertices are given either in clockwise or counterclockwise order. Each of the following m lines of input contains four numbers; these are x and y coordinates of the two points defining the cutting line. If a vertex of the polygon is closer than 10e-8 to the cutting line then we consider that the vertex lies on the cutting line.
Input is terminated by a line with n and m equal to 0.

输出:

For each cutting line, print the total length of the segments in the intersection of the line and the polygon defined for this test case, with 3 digits after the decimal point. Note: the perimiter of a polygon belongs the polygon.
The picture above illustrates the first cutting line for the polygon from the sample.

样例输入:

9 5
0 0
0 2
1 1
2 2
3 1
4 2
5 1
6 2
6 0
-1 2 7.5 1
0 1 6 1
0 1.5 6 1.5
0 2 6 1
0 0 0 2
0 0

样例输出:

2.798
6.000
3.000
2.954
2.000

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1154

首先这个题目用到的知识点比较多,而且,思想也很好,精度也有要求,做这个题目对计算几何的要求还是有一点的

表示这个题目不是像杭电上标难度1的那么好做;

首先用到很多模板,模板的精度和正确性一定要保证

其次就是这个题目到底是怎么做

解题思路:求出直线与所有多边形的交点,然后按照交点排序,按照X从左到右排序,那么任意两个相邻之间的点的连线线段如果在

这个多边形内部那么中点一定是在这个多边形内部,然后基本上注意几个细节就搞定了

细节一:这个相交要求是直线与线段的非规范相交,也就是端点相交也算,如果这个题目相交于某个端点呢,也不怕,因为只要相交

于某个端点,那么就一定是两次,两次同样的点排序后一定还是在一起,这个情况就不用考虑了,如果不是非规范相交,那么万一一

个交于端点一个交于非端点就完了;

细节二:如果多边形的某个边与在这条直线上,那么这条线段的两个端点全部加入到点的集合里面,否则会漏解

代码(好长的说):

#include <iostream>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define maxn 1200
#define eps 1e-8
struct point
{
    double x;
    double y;
}po[maxn],rec[maxn];
struct line
{
    point a;
    point b;
}temp,temp1;
double xmulit(point &a,point &b,point &c)
{
    return (a.x-b.x)*(a.y-c.y)-(a.y-b.y)*(a.x-c.x);
}
bool across(point &a,point &b,point &c,point &d)//直线ab和线段cd是否相交
{
double p=xmulit(a,b,c),p1=xmulit(a,b,d);
if( fabs(p1) <= eps || fabs(p) <= eps ) return true;
if( p*p1 < -eps )
return true;
return false;
}
bool one_line(point &a,point &b,point &c,point &d)//直线ab和线段cd是否相交
{
double p=xmulit(a,b,c),p1=xmulit(a,b,d);
if( fabs(p1) < eps && fabs(p) < eps ) return true;
return false;
}
bool is_equal(point &a,point &b)//判断点a和点b是否相等
{
return (fabs(a.x-b.x) <= eps) && (fabs(a.y-b.y) <=eps);
}
point intersection(line &u,line &v)
{
point ret=u.a;
double t=((u.a.x-v.a.x)*(v.a.y-v.b.y) - (u.a.y-v.a.y)*(v.a.x-v.b.x))/((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));
ret.x+=(u.b.x-u.a.x)*t;
ret.y+=(u.b.y-u.a.y)*t;
return ret;
}
int n,m;
double dis(point &a,point &b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int cmp(point a, point b)
{
    if(fabs(a.x-b.x)<eps)
        return a.y<b.y;
    return a.x<b.x;
}
bool on_segment(point pi,point pj,point pk)//判断点pk时候在线段pi, pj上
{
    if(xmulit(pi, pj, pk)==0)
    {
        if(pk.x>=min(pi.x,pj.x)&&pk.x<=max(pi.x,pj.x)&&pk.y>=min(pi.y,pj.y)&&pk.y<=max(pi.y,pj.y))
            return true;
    }
    return false;
}
bool segments_intersect(point p1,point p2,point p3,point p4)//判断线段是否相交
{
    double d1=xmulit(p3,p4,p1);
    double d2=xmulit(p3,p4,p2);
    double d3=xmulit(p1,p2,p3);
    double d4=xmulit(p1,p2,p4);
    if(d1*d2<0&&d3*d4<0)
        return true;
    else if(d1==0&&on_segment(p3,p4,p1))
        return true;
    else if(d2==0&&on_segment(p3,p4,p2))
        return true;
    else if(d3==0&&on_segment(p1,p2,p3))
        return true;
    else if(d4==0&&on_segment(p1,p2,p4))
        return true;
    return false;
}
int inpoto(point a)//判断点是否在多边形的内部
{
    int i;
    point b,c,d;
    b.y=a.y;
    b.x=1e15;//定义射线
    int flag=0;
    int count=0;
    for(i=0;i<n;i++)
    {
        c = po[i];
        d = po[i + 1];
        if(on_segment(c,d,a))//该点在多边形的一条边上
            return 1;
        if(abs(c.y-d.y)<eps)
            continue;
        if(on_segment(a,b,c))//和顶点相交的情况,如果y值较大则取
        {
            if(c.y>d.y)
                count++;
        }
        else if(on_segment(a,b,d))//和顶点相交的情况,如果y值较大则取
        {
            if(d.y>c.y)
                count++;
        }
        else if(segments_intersect(a,b,c,d))//和边相交
            count++;
    }
    return count%2;//当L和多边形的交点数目C是奇数的时候,P在多边形内,是偶数的话P在多边形外。
}
point mid(point &a,point &b)
{
    point c;
    c.x=(a.x+b.x)/2;
    c.y=(a.y+b.y)/2;
    return c;
}
double find_ans()
{
    point a,b;
    int i,j,k,pos=0;
    double ans=0;
    po[n]=po[0];
    for(i=0;i<n;i++)
    {
        if(one_line(temp.a,temp.b,po[i],po[i+1]))
        {
          rec[pos++]=po[i];
          rec[pos++]=po[i];
          continue;
        }
        if(across(temp.a,temp.b,po[i],po[i+1]))
        {
          temp1.a=po[i],temp1.b=po[i+1];
          rec[pos++]=intersection(temp,temp1);
        }
    }
    sort(rec,rec+pos,cmp);
    for(i=0;i<pos-1;i++)
    {
       if(inpoto(mid(rec[i],rec[i+1])))
          ans+=dis(rec[i],rec[i+1]);
    }
    return ans;
}
int main()
{
    int i,j,k;
    while(scanf("%d%d",&n,&m))
    {
        if(m==0 && m==0)
        return 0;
        for(i=0;i<n;i++)
        scanf("%lf%lf",&po[i].x,&po[i].y);
        for(i=0;i<m;i++)
        {
            scanf("%lf%lf%lf%lf",&temp.a.x,&temp.a.y,&temp.b.x,&temp.b.y);
            printf("%.3lf\n",find_ans());
        }
    }
    return 0;
}


  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮