about 4 years ago

该好好反思一下20天来干了些啥了……也就做了一点点比赛然后啥都没了吧……sighsighsigh怎么能这么弱
还要好好反思一下手残……真是太可怕了……想当然就是不可以啊
-------------正题的分割线----------------------------------

sol:

考虑正向做。就是二分然后判断,但是一个带圆弧的图形覆盖实在是太难求……
所以有了莫涛大大的论文。恩讲的很详细。主要的思想就是爆搜的神剪枝。
把路线拆成线段,如果当前结果已经覆盖了这条线段,那么就把这条线段扔掉,否则的话拆开加入待处理线段。用一个队列就好了
但是如何判断呢?那么问题来了=w=
设线段ab,a与陆地的最近点为p,b与陆地的最近点为q
二分得到ab上的点r 则r到陆地的最近距离<=min(rp,rq)
设l=min(rp,rq) 即此时分别以p,q为圆心,画半径为l的圆,一定能覆盖这个线段
若l<=ans 舍去,不更新答案。
若l>ans 加入队列
因为每次更新答案是在暴力计算点到所有线段最近距离的时候,某点到所有线段的最近距离必<=ans
所以ans可以再此时不断取最大得到
-----想了好久的证明-----sigh-------------------------------------------

新技能:

1、判断点在线段上
判断他们在一条直线上+点的横纵坐标不超过端点的横纵坐标
2、两条线段是否相交
对每一条线段,判断另一条线段是否在这条线段的两侧【必须对两条线段都做】
3、求两条线段的交点
用相似三角形的比来确定距离
4、判断点是否在多边形内(射线法)
这里犯了一个错误,不应该用给定的这两条线段的端点,而应该自己判断出这条线段的较小端点和较大端点
假设向左引射线
若线段与y轴平行,忽略
为了防止正好过端点导致计算两次,假设每条线段下闭上开
即若与较小点y相等,则若相交则++
若与较大点y相等,则忽略
然后在其他情况里判相交
5、计算点到线段的距离
如果点是到端点距离较小(用点积判断),返回端点
否则引一条法向量求交点

总结一下错掉的地方……

1、射线法
2、点积叉积弄混
3、新入待处理线段时入错线段了……
4、写重载,再不写重载就要剁手了
静态查错!

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#define eps 1e-7
#define inf 100001
using namespace std;
int c,n;double answer=0.0;
struct point
{
    double x,y;
    point(double xx=0.0,double yy=0.0){x=xx,y=yy;}
    void print(){printf("%lf %lf ",x,y);}
    void read(){scanf("%lf%lf",&x,&y);}
};
double length(point a) {return sqrt(a.x*a.x+a.y*a.y);}
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);}
double dot(point a,point b){return a.x*b.x+a.y*b.y;} 
double cross(point a,point b){return a.x*b.y-b.x*a.y;}
point spin(point a){return point(-a.y,a.x);}
double fabs(double num){if (num>0) return num;return -num;}
int dcmp(double x,double y)
{
    if (fabs(y-x)<eps) return 0;
    if (x<y) return -1;return 1;
}
bool ison(point a,point b,point c)
{
    if (dcmp(cross(b-a,b-c),0)==0)
        if (dcmp(a.x,max(b.x,c.x))<=0&&dcmp(a.x,min(b.x,c.x))>=0&&dcmp(a.y,max(b.y,c.y))<=0&&dcmp(a.y,min(b.y,c.y))>=0)   return true;
    return false;
}
bool isinter(point a,point b,point c,point d)
{
    if ((dcmp(cross(b-a,c-a)*cross(b-a,d-a),0))<=0&&(dcmp(cross(d-c,a-c)*cross(d-c,b-c),0)<=0)) return true;
    return false;
}
point getinter(point a,point da,point c,point dc)
{
    point v=c-a;
    double k=cross(da,v)/cross(dc,da);
    return c+point(k*dc.x,k*dc.y);
}
struct polygon
{
    point a[41];int num;
    void read()
    {
        scanf("%d",&num);
        for (int i=0;i<num;i++) scanf("%lf%lf",&a[i].x,&a[i].y);//a[i].read();
 }
    bool ifin(point now)
    {
        int i,j,sum=0;double minn,maxx;
        for (i=0;i<num;i++)if (ison(now,a[i],a[(i+1)%num])) return true;
        point p=point(-10001,now.y);
        for (i=0;i<num;i++)
        {
            j=(i+1)%num;
            if (dcmp(a[i].y,a[j].y)!=0)
            {
                minn=min(a[i].y,a[j].y),maxx=max(a[i].y,a[j].y);
                if (dcmp(now.y,minn)==0) {if(isinter(p,now,a[i],a[j]))sum++;continue;}
                if (dcmp(now.y,maxx)==0) {continue;    }
                if (isinter(p,now,a[i],a[j]))   sum++; 
            }
        }
        return sum&1;
    }
} island[21];
struct con
{
    point a;double dis;
    con() {}
    con (point x,double y=0.0) {a=x;dis=y;}
};
struct line
{
    point a,b;
    line(){}
    line (point x,point y) {a=x;b=y;}
};
con dist(point a,point b,point c)
{//点积! 
 if (dcmp(dot(c-b,a-b),0)<=0)return con(b,length(a-b));
    if (dcmp(dot(a-c,b-c),0)<=0)return con(c,length(a-c));
    point dir=spin(c-b);
    point now=getinter(a,dir,b,c-b);
    return con(now,length(a-now));
}
point getdist(point a)
{
    con temp(a,inf);int i,j,k;
    for (i=1;i<=c;i++)
        if (island[i].ifin(a)) return a; 
    for (i=1;i<=c;i++)
        for (j=0;j<island[i].num;j++)
            {
                k=(j+1)%island[i].num;
                con result=dist(a,island[i].a[j],island[i].a[k]);
                if (result.dis<temp.dis) temp=result;
            }
    if (temp.dis>answer)answer=temp.dis;
    return temp.a;
}
queue<line>q;
point route[21];
int main()
{
    scanf("%d%d",&c,&n);
    answer=0.0;
    int i,j;point left,right,mid,r1,r2;line now;double k1,k2,t;
    for (i=0;i<n;i++)    route[i].read();
    for (i=1;i<=c;i++) island[i].read();
    for (i=0;i<n-1;i++)q.push(line(route[i],route[i+1]));//!!n-1
 while (!q.empty())
    {
        now=q.front();q.pop();
        r1=getdist(now.a);
        r2=getdist(now.b);
        left=now.a;right=now.b;
        while (length(right-left)>=1e-5)//限制! 
     {
            mid=(left+right);
            mid.x/=2;mid.y/=2;
            k1=length(mid-r1);k2=length(mid-r2);
            if(k1-k2<0) left=mid;else right=mid;
        }
        mid=(left+right);mid.x/=2;mid.y/=2;
        k1=length(mid-r1);k2=length(mid-r2);
        t=max(k1,k2);
        if (t-answer>0.0005) {q.push(line(now.a,mid));q.push(line(mid,now.b));}
    }
    printf("%.2lf\n",answer);
}
← 【bzoj2957】【线段树】【神做法】楼房重建 【bzoj1294】【状压dp】围豆豆 →
 
comments powered by Disqus