2014
11-05

# Draw

huicpc0860 likes drawing,but not good at drawing.One day, he gets a software of drawing.
The software provides a eraser B,you can consider it like a convex hull. Yet, the eraser can make your draw from black to white.Now give you a black convex hull A which you can consider like a drawing, and a white convex hull which is a eraser.Now, we only know the angle a between the eraser’s moving direction and the x-axis,and I want to move the eraser the least distance to make the remaind part area of the drawing is K percent of the original’s.

First line is the number of soiled area A’s vectors NA(3<=NA<=100).Follows NA lines, describes the convex polygon counterclockwise, each line has two decimal xi, yi ( -10000 ≤ xi, yi ≤ 10000) representatives one vector’s coordinate.
Then, another line is the number of soiled area B’s vectors NB(3<=NB<=100).Follows NB lines, describes the convex polygon counterclockwise, each line has two decimal xi, yi ( -10000 ≤ xi, yi ≤ 10000) representatives one vector’s coordinate.
Lastest line has two decimal, a and K.a (0 ≤a< 360)is the direction’s angle with x positive axis and K is the rate.

First line is the number of soiled area A’s vectors NA(3<=NA<=100).Follows NA lines, describes the convex polygon counterclockwise, each line has two decimal xi, yi ( -10000 ≤ xi, yi ≤ 10000) representatives one vector’s coordinate.
Then, another line is the number of soiled area B’s vectors NB(3<=NB<=100).Follows NB lines, describes the convex polygon counterclockwise, each line has two decimal xi, yi ( -10000 ≤ xi, yi ≤ 10000) representatives one vector’s coordinate.
Lastest line has two decimal, a and K.a (0 ≤a< 360)is the direction’s angle with x positive axis and K is the rate.

4
0 0
2 0
2 2
0 2
4
-2 0
-1 0
-1 1
-2 1
0 0.75
3
-2 -1
-1 0
-2 1
3
1 -1
2 0
1 1
180 0.5

2.0000
2.7071

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<cmath>
#include<vector>
#include<algorithm>
#define eps 1e-8
#define inf 0x3f3f3f3f
#define N 10100
#define pi acos(-1.0)
using namespace std;
int Sig(double a)
{
return a<-eps?-1:a>eps;
}
struct Point
{
double x,y;
Point(){}
Point(double x0,double y0):x(x0),y(y0){}
void in()
{
scanf("%lf%lf",&x,&y);
}
double len()
{
return sqrt(x*x+y*y);
}
double operator ^(Point pt)
{
return pt.x*x+pt.y*y;
}
Point operator -(Point pt)
{
return Point(x-pt.x,y-pt.y);
}
Point operator +(Point pt)
{
return Point(x+pt.x,y+pt.y);
}
Point operator *(double t)
{
return Point(x*t,y*t);
}
Point operator /(double t)
{
return Point(x/t,y/t);
}
};
struct Polygon
{
Point p[220];
int n;
void in()
{
for(int i=0;i<n;i++)
p[i].in();
}
};
double Xmult(Point o,Point a,Point b)
{
return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}
double Dis(Point a,Point b)
{
return (a-b).len();
}
int con[300];
int cn;//í1°üμ??￥μ?êy
Point po;
int cmp(Point a,Point b)
{
double d=Xmult(po,a,b);
if(d>0)
return 1;
if(d==0 && Dis(a,po)<Dis(b,po))
return 1;
return 0;
}
void Graham(Point p[],int &n)
{
int i,ind=0;
for(i=1;i<n;i++)
if(p[ind].y>p[i].y || (p[ind].y==p[i].y && p[ind].x>p[i].x))
ind=i;
swap(p[ind],p[0]);
po=p[0];
sort(p+1,p+n,cmp);
con[0]=0;
con[1]=1;
cn=1;
for(i=2;i<n;i++)
{
while(cn>0 && Sig(Xmult(p[con[cn-1]],p[con[cn]],p[i]))<=0)
cn--;
con[++cn]=i;
}

int tmp=cn;
for(i=n-2;i>=0;i--)
{
while(cn>tmp && Sig(Xmult(p[con[cn-1]],p[con[cn]],p[i]))<=0)
cn--;
con[++cn]=i;//p[cn]==p[0];
}
Point pt[210];
for(int i=0;i<cn;i++)
pt[i]=p[con[i]];
for(int i=0;i<cn;i++)
p[i]=pt[i];
n=cn;
}
Point Intersection(Point u1,Point u2,Point v1,Point v2)
{
Point ret=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));
ret.x+=(u2.x-u1.x)*t;
ret.y+=(u2.y-u1.y)*t;
return ret;
}
double Area(Point p[],int n)
{
double s=0;
for(int i=0;i<n;i++)
s+=Xmult(Point(0,0),p[i],p[(i+1)%n]);
return fabs(s)*0.5;
}
double Get_inter(Polygon p1,Polygon p2)
{
Polygon tmp,newp;
newp=p2;
for(int i=0;i<p1.n;i++)
{
Point a=p1.p[i];
Point b=p1.p[(i+1)%p1.n];
tmp.n=0;
for(int j=0;j<newp.n;j++)
{
int r1=Sig(Xmult(a,b,newp.p[j]));
int r2=Sig(Xmult(a,b,newp.p[(j+1)%newp.n]));
if(r1>=0)
tmp.p[tmp.n++]=newp.p[j];
if(r1*r2<0)
{
Point pp=Intersection(a,b,newp.p[j],newp.p[(j+1)%newp.n]);
tmp.p[tmp.n++]=pp;
}
}
newp=tmp;
}
return Area(newp.p,newp.n);
}
double Work(Polygon p1,Polygon p2,Point v,double ks,double all)
{
Polygon tmp;
double left=0,right=inf;
double mid;
while(right-left>eps)
{
mid=(left+right)*0.5;
tmp=p1;
for(int i=0;i<tmp.n;i++)
tmp.p[tmp.n+i]=tmp.p[i]+v*mid;
tmp.n*=2;
Graham(tmp.p,tmp.n);
double s=Get_inter(tmp,p2);
if(Sig(all-s-ks)<=0)
right=mid-eps;
else
left=mid+eps;
}
return left;
}
int main()
{
//	freopen( "in.txt", "r", stdin );
Polygon p1,p2;
Point v;
double k,ange;
while(scanf("%d",&p2.n)!=EOF)
{
p2.in();
scanf("%d",&p1.n);
p1.in();
scanf("%lf%lf",&ange,&k);
ange=ange/360*2*pi;
v=Point(cos(ange),sin(ange));
v=v/v.len();
double s=Area(p2.p,p2.n);
Polygon tmp=p1;
for(int i=0;i<tmp.n;i++)
{
tmp.p[tmp.n+i]=tmp.p[i]+v*inf;
}
tmp.n*=2;
Graham(tmp.p,tmp.n);
//    for( int i = 0; i < tmp.n; i++ ){
//    	cout<<tmp.p[i].x<<" "<<tmp.p[i].y<<endl;
//    }
double s1=s-Get_inter(p1,p2);
double s2=s-Get_inter(tmp,p2);
//      cout<<s<<" "<<s1<<" "<<s2<<endl;
if(Sig(s1-s*k)<0 || Sig(s2-s*k)>0)
{
printf("-1\n");
continue;
}
printf("%.4f\n",Work(p1,p2,v,k*s,s));
}
return 0;
}

1. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。

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

3. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？

4. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。