首页 > ACM题库 > HDU-杭电 > HDU 3520-Draw[解题报告]HOJ
2014
11-05

HDU 3520-Draw[解题报告]HOJ

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.

Lucky Coins Sequence

输入:

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,比楼主的要快。