tkdsheep-ZOJ2318

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
给出n个圆形岛屿的坐标以及半径，你乘坐着一艘船，这个船也是一个圆，船的初始坐标和半径也会给出，问能不能驾驶船脱离这些圆形小岛的包围

首先将所有圆平移，使船的圆心在原点上，然后把所有圆的半径加上船的半径，这样船就变成了一个点

对于两个【相交】的圆，连接圆心构成一条线段，那么船肯定不能穿过这些线段，所以题目变成了给出很多线段，问能不能找到一个包围原点的多边形

接下来的具体做法在shi哥的解体报告里说的比较清楚了，但我很土，一开始没搞懂有向角是什么东西。。也明白为什么要spfa求个最短路。。

实际上有向角说形象点就是判断顺时针还是逆时针，比如圆心i和圆心j，如果j在i的顺时针方向，则i到j的边权值为正，j到i的边权值为负，逆时针类似

总之就是方向不同，则权值的正负要对应上，判方向可以用叉积

然后spfa并不是为了做最短路，而是单纯判个负环而已，因为有负环就说明有多条线段连通构成了-2Pi的多边形

另外此题精度要求高，需要eps，对于相切的圆，点是依然可以从那条缝中穿过的
}}}

{{{

#include <iostream>
#include <queue>
#include <cmath>
#include <cstdio>
#include <set>
//#include <map>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <cassert>
#define MAX 1000000000
#define eps 1e-10
using namespace std;
//Never lose hope~ For the dream 


double x[300];
double y[300];
double r[300];
double l[300];//每个圆心到原点的距离 
struct node
{
    int x;
    double len;
};

vector <node> e[300];//edge
bool in[300];
int c[300];
double d[300];


int main()
{
    int re,i,j,k;
    double X,Y,len,R;
    node ss,tt; 
    cin>>re;
    while(re--)
    {

        int n;
        cin>>n;
        for(i=0;i<n;i++)
        {
            e[i].clear();
            cin>>x[i]>>y[i]>>r[i];
        }
        cin>>X>>Y>>R;
        for(i=0;i<n;i++)
        {
            x[i]-=X;
            y[i]-=Y;
            r[i]+=R;
            l[i]=sqrt(x[i]*x[i]+y[i]*y[i]); 
        }

        for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
        {
            double len=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
            if(len+eps>r[i]+r[j])//不相交，注意精度 
            continue;

            double chaji=x[i]*y[j]-x[j]*y[i];
            double angle=acos((l[i]*l[i]+l[j]*l[j]-len*len)/2/l[i]/l[j]);


            if(chaji>=0)//j在i的顺时针方向
            {
                ss.x=j;
                ss.len=angle;
                e[i].push_back(ss);
                ss.x=i;
                ss.len=-angle;
                e[j].push_back(ss);      
            }
            else
            {
                ss.x=j;
                ss.len=-angle;
                e[i].push_back(ss);
                ss.x=i;
                ss.len=angle;
                e[j].push_back(ss);
            } 
        }

        queue <int> q;
        for(i=0;i<n;i++)
        { 
            q.push(i);
            in[i]=true; 
            d[i]=c[i]=0;
        }

        bool ff=true;

        while(!q.empty())
        {
            ss.x=q.front();
            q.pop();
            in[ss.x]=false;
            c[ss.x]++;
            if(c[ss.x]>n)
            {
                ff=false;
                break;
            }
            for(i=0;i<e[ss.x].size();i++)
            {
                tt.x=e[ss.x][i].x;
                tt.len=d[ss.x]+e[ss.x][i].len;
                if(tt.len+eps<d[tt.x])//注意精度 
                {
                    d[tt.x]=tt.len;
                    if(!in[tt.x])
                    {
                        in[tt.x]=true;
                        q.push(tt.x);
                    }
                }

            }
        }

        if(ff)
        cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
        if(re)
        cout<<endl;

    }
    return 0;
}

}}}

给出n个圆形岛屿的坐标以及半径，你乘坐着一艘船，这个船也是一个圆，船的初始坐标和半径也会给出，问能不能驾驶船脱离这些圆形小岛的包围
首先将所有圆平移，使船的圆心在原点上，然后把所有圆的半径加上船的半径，这样船就变成了一个点
对于两个【相交】的圆，连接圆心构成一条线段，那么船肯定不能穿过这些线段，所以题目变成了给出很多线段，问能不能找到一个包围原点的多边形
接下来的具体做法在shi哥的解体报告里说的比较清楚了，但我很土，一开始没搞懂有向角是什么东西。。也明白为什么要spfa求个最短路。。
实际上有向角说形象点就是判断顺时针还是逆时针，比如圆心i和圆心j，如果j在i的顺时针方向，则i到j的边权值为正，j到i的边权值为负，逆时针类似
总之就是方向不同，则权值的正负要对应上，判方向可以用叉积
然后spfa并不是为了做最短路，而是单纯判个负环而已，因为有负环就说明有多条线段连通构成了-2Pi的多边形
另外此题精度要求高，需要eps，对于相切的圆，点是依然可以从那条缝中穿过的

#include <iostream>
#include <queue>
#include <cmath>
#include <cstdio>
#include <set>
//#include <map>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <cassert>
#define MAX 1000000000
#define eps 1e-10
using namespace std;
//Never lose hope~ For the dream 
double x[300];
double y[300];
double r[300];
double l[300];//每个圆心到原点的距离 
struct node
{
    int x;
    double len;
};
vector <node> e[300];//edge
bool in[300];
int c[300];
double d[300];
int main()
{
    int re,i,j,k;
    double X,Y,len,R;
    node ss,tt; 
    cin>>re;
    while(re--)
    {
        int n;
        cin>>n;
        for(i=0;i<n;i++)
        {
            e[i].clear();
            cin>>x[i]>>y[i]>>r[i];
        }
        cin>>X>>Y>>R;
        for(i=0;i<n;i++)
        {
            x[i]-=X;
            y[i]-=Y;
            r[i]+=R;
            l[i]=sqrt(x[i]*x[i]+y[i]*y[i]); 
        }
        for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
        {
            double len=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
            if(len+eps>r[i]+r[j])//不相交，注意精度 
            continue;
            double chaji=x[i]*y[j]-x[j]*y[i];
            double angle=acos((l[i]*l[i]+l[j]*l[j]-len*len)/2/l[i]/l[j]);
            if(chaji>=0)//j在i的顺时针方向
            {
                ss.x=j;
                ss.len=angle;
                e[i].push_back(ss);
                ss.x=i;
                ss.len=-angle;
                e[j].push_back(ss);      
            }
            else
            {
                ss.x=j;
                ss.len=-angle;
                e[i].push_back(ss);
                ss.x=i;
                ss.len=angle;
                e[j].push_back(ss);
            } 
        }
        queue <int> q;
        for(i=0;i<n;i++)
        { 
            q.push(i);
            in[i]=true; 
            d[i]=c[i]=0;
        }
        bool ff=true;
        while(!q.empty())
        {
            ss.x=q.front();
            q.pop();
            in[ss.x]=false;
            c[ss.x]++;
            if(c[ss.x]>n)
            {
                ff=false;
                break;
            }
            for(i=0;i<e[ss.x].size();i++)
            {
                tt.x=e[ss.x][i].x;
                tt.len=d[ss.x]+e[ss.x][i].len;
                if(tt.len+eps<d[tt.x])//注意精度 
                {
                    d[tt.x]=tt.len;
                    if(!in[tt.x])
                    {
                        in[tt.x]=true;
                        q.push(tt.x);
                    }
                }
            }
        }
        if(ff)
        cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
        if(re)
        cout<<endl;
    }
    return 0;
}