#1231 : Border Length
描述
Garlic-Counting Chicken is a special species living around the Lake of Peking University.
A Garlic-Counting Chicken always flies out from home in the morning, goes to some fixed points looking for buuugs(a kind of worm), and comes back home in the afternoon.
Students from the School of Life Sciences find that, a Garlic-Counting Chicken always flies a straight line between two points, and its trace never goes across itself. The students want to find out the relationship between Garlic-Counting Chicken and the Lake. So they ask you to calculate the length of border of the common area between the Lake and one Garlic-Counting Chicken's daily trace.
输入
There are no more than 10 test cases.
For each test case, the first line contains n, the number of points on the trace in order. 1<=n<=1000.
Then n lines follow. Each line is a pair of integer x, y representing the n points' coordinates in order.
The last line contains three integers x,y and r descripting the Lake, The Lake is a circle. Its center is at (x,y) and its radius is r.
The input ends if n = 0.
All |x|, |y|, |r| are smaller than 107.
输出
For each test case, output the length of the border of the common area. Please round the answer to the closest integer.
- 样例输入
-
4
-10 -10
-10 10
10 10
10 -10
-10 -10 20
4
-10 -10
-10 10
10 10
10 -10
-10 -10 4
4
-10 -10
-10 10
10 10
10 -10
0 0 10
4
-40 -40
-40 40
40 40
40 -40
0 0 50
0 - 样例输出
-
71
14
63
297
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <cstdio>
using namespace std;
const double eps=0.000000000001;
const double PI=acos(-1.0);
const int maxn=;
int dcmp(double a)
{
if(fabs(a)<eps)return ;
else return a>?:-;
}
struct Point
{
double x,y;
Point(double cx=,double cy=)
{
x=cx; y=cy;
}
double ang;
void Angle()
{
ang=atan2(y,x);
if(ang<){
ang+=*PI;
}
}
bool operator <(const Point &rhs)const
{
return ang<rhs.ang;
}
};
struct Circle
{
Point c;
double r;
Circle(Point cc=Point(,),double cr=)
{
c=cc; r=cr;
}
Point point(double a)
{
return Point(c.x+cos(a)*r, c.y+sin(a)*r);
}
};
Point operator -(Point A, Point B)
{
return Point(A.x-B.x,A.y-B.y);
}
Point operator +(Point A, Point B)
{
return Point(A.x+B.x,A.y+B.y);
}
bool operator ==(const Point &A, const Point &B)
{
return dcmp(A.x-B.x) == && dcmp(A.y-B.y)==;
}
double Dot(Point A,Point B)
{
return A.x*B.x+A.y*B.y;
}
double Length(Point A)
{
return sqrt(Dot(A,A));
}
double Cross(Point A, Point B)
{
return A.x*B.y - A.y*B.x;
}
Point TE[maxn];
Circle C;
struct Ins{
Point c;
int id;
}Poi[maxn];
struct Line
{
Point p;
Point v;
Line(Point cp=Point(,),Point cv=Point(,))
{
p=cp; v=cv;
}
Point point(double a)
{
Point te=Point(v.x*a,v.y*a);
return p+te;
}
};
int getLineCicleIntersection(Line L,Circle C, double &t1,double &t2,Point &A,Point &B)
{
double a=L.v.x,
b=L.p.x-C.c.x,
c=L.v.y,
d=L.p.y-C.c.y;
double e=a*a+c*c,
f=*(a*b+c*d),
g=b*b+d*d-C.r*C.r;
double delta=f*f-*e*g;
if(dcmp(delta)<)return ;
if(dcmp(delta)==)
{
t1=t2=-f/(*e);A=L.point(t1);
return ;
}
t1=(-f - sqrt(delta))/(*e);
A=L.point(t1);
t2=(-f + sqrt(delta))/(*e);
B=L.point(t2);
return ;
}
int judjiaodian(int n)
{
int nu=;
double t1,t2;
Point A,B;
for(int i=; i<n; i++)
{
int ge=getLineCicleIntersection(Line(TE[i],TE[i+]-TE[i]),C,t1,t2,A,B);//计算直线和圆交点 大白书模板
if(ge==)continue;
double s=Length(TE[i]-TE[i+]);
double d1=Length(TE[i]-A);
double d2=Length(TE[i+]-A);
if(ge==){
if(dcmp(s-d1)>=&&dcmp(s-d2)>=) //判断是否在这条边上
{
Poi[nu].c=A; Poi[nu].id=i; nu++;
}
continue;
}
double d3=Length(TE[i]-B);
double d4=Length(TE[i+]-B);
if(dcmp(s-d1)>=&&dcmp(s-d2)>=&&dcmp(s-d3)>=&&dcmp(s-d4)>=)//如果存在两个点
{
if(d1>d3){//应该把离起点进的点放在前面
swap(A,B);
}
Poi[nu].c=A; Poi[nu].id=i;nu++;
Poi[nu].c=B; Poi[nu].id=i;nu++;
}else if(dcmp(s-d1)>=&&dcmp(s-d2)>=)
{
Poi[nu].c=A; Poi[nu].id=i;nu++;
}else if(dcmp(s-d3)>=&&dcmp(s-d4)>=)
{
Poi[nu].c=B; Poi[nu].id=i;nu++;
}
}
int ge=;
for(int i=; i<nu; i++)
if( (Poi[i].c==Poi[ge-].c) == false )
Poi[ge++]=Poi[i];
nu=ge;
return nu;
}
int isPointInpolygon(Point p,int n)//判断点是否在多边形内
{
int wn=;
for(int i=; i<n; i++)
{
int k=dcmp(Cross(TE[i+]-TE[i],p-TE[i]));
int d1=dcmp(TE[i].y -p.y );
int d2=dcmp(TE[i+].y-p.y);
if( k > && d1 <= && d2 > )wn++;
if( k < && d2 <= && d1 > )wn--;
}
if(wn!=)return ;
return ;
}
void solve(int n)
{
int numOfInCir=;
double dist=;
for(int i=; i<n; i++)
{
if( dcmp( C.r-Length(TE[i]-C.c) )>= )numOfInCir++;
dist+=Length( TE[i+]-TE[i] );
}
if(isPointInpolygon(C.c,n))
{
if(numOfInCir==n){
printf("%.0lf\n",dist);
}else printf("%.0lf\n",PI**C.r);
return;
}
if(numOfInCir == n)
{
printf("%.0lf\n",dist);
}else printf("0\n");
}
Point Hu[maxn];
double judsolveCir(int nu,int n)
{
for(int i=; i<nu; i++)
{
Hu[i]=Poi[i].c-C.c;
Hu[i].Angle();
}
sort(Hu,Hu+nu);
Hu[nu]=Hu[];
Hu[nu].ang+=*PI;
double ans=;
for(int i=; i<nu; i++)
{
double ang=(Hu[i].ang+Hu[i+].ang)/;
if(ang>*PI)ang-=*PI;
Point t =C.point(ang);
if(isPointInpolygon(t,n))
{
ang=Hu[i+].ang-Hu[i].ang;
ans+=ang*C.r;
}
}
return ans;
}
Point TP[maxn];
double judsolvePoly(int nu, int n)
{
int loc=,num=;
for(int i=; i<n; i++)//融合那些点
{
TP[num++]=TE[i];
while(loc<nu&&Poi[loc].id<=i){
TP[num++]=Poi[loc].c; loc++;
}
}
loc=;
for(int i=; i<num; i++)
if((TP[i]==TP[loc-])==false )TP[loc++]=TP[i];
num=loc;
TP[num]=TP[];
double ans=;
for(int i=; i<num; i++)
{
Point tt=TP[i]+TP[i+];
tt.x*=0.5;
tt.y*=0.5;
double d1=Length(C.c-tt);
if(dcmp(C.r-d1)>=){
ans+=Length(TP[i+]-TP[i]);
}
}
return ans;
}
int main()
{
int n;
while(scanf("%d",&n)==&&n)
{
for(int i=; i<n; i++)
scanf("%lf%lf",&TE[i].x,&TE[i].y);
TE[n]=TE[];
scanf("%lf%lf%lf",&C.c.x,&C.c.y,&C.r);
int nu=judjiaodian(n);//计算交点
if(nu==||nu==){
solve(n);// 特判那几种情况
continue;
}
double ans=judsolveCir(nu,n);// 计算圆在多边形内的部分
ans+=judsolvePoly(nu,n);// 计算多边形在圆内的部分
printf("%.0lf\n",ans);
}
return ;
}
题意: