2013
12-03

# 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

#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)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮