[ZOJ1030 Farmland]【狗狗40题】【计算几何】【绕圈圈】【判点是否在多边形内】

【题目大意】

给定一个简单平面无向图。n<=200。每个点给出坐标

问图中包含边数为k的圈有多少个。

这些圈要满足：

1、面积>0

2、不能有其它的点或者边在圈内

【算法分析】

和大妈题#3的area(ZOJ2361)差不多。

先枚举起始边，然后对于路径中最后的两个点，x,z，构成向量x->z，然后再在与x相连的点集里找一个点y，满足x->z逆时针绕到x->y所夹的角最大。

然后就这样绕，注意每条边x->y只能走一次。因为从x->y绕多一遍只能绕出之前绕过的圈。方向不同(y->x)分开看待。

当我们找到一开始那个点时，实际就找到了圈了。

但是我们可能顺时针算了这个圈一次，逆时针又算了一次。而实际上，如果走逆时针走重复的话，必然和本次的起始点是一样的。

于是每次加答案时只需要判判把整条路径逆过来有没有出现过就行了。(我直接set < vector

然后再枚举看圈圈内有没有其它的点在。

这个要用到判点是否在多边形内。

基本上就这样。

【其它】

好像无论多暴力都0MS。

2Y。一开始没有注意到可能有杂点可能在多边形

T_T，好长好长

【CODE】

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

const int N=256;

const double eps=1e-7;

const double INF=1e50;

const double pi=acos(-1);

 

int sign(double x){

    if (x<-eps) return -1;

    if (x> eps) return  1;

    return 0;

}

 

struct TPoint {double x,y;};

 

TPoint operator – (TPoint A,TPoint B){

    TPoint ret;

    ret.x=A.x-B.x;

    ret.y=A.y-B.y;

    return ret;

}

 

double operator ^ (TPoint A,TPoint B){

    return A.x*B.y-A.y*B.x;

}

 

double operator * (TPoint A,TPoint B){

    return A.x*B.x+A.y*B.y;

}

 

double Length(TPoint v){

    return sqrt(v.x*v.x+v.y*v.y);

}

 

double Get_Angle(TPoint v1,TPoint v2){

    return acos(v1*v2/Length(v1)/Length(v2));

}

 

bool On_Seg(TPoint p,TPoint A,TPoint B){

    if (sign((p-A)^(B-A))!=0) return false;

    if (min(A.x,B.x)<=p.x+eps && p.x<=max(A.x,B.x)+eps

    &&  min(A.y,B.y)<=p.y+eps && p.y<=max(A.y,B.y)+eps)

      return true;

    return false;

}

 

bool Seg_Cross(TPoint p1,TPoint p2,TPoint p3,TPoint p4){

    return

    sign( ( (p2-p1) ^ (p3-p1) ) * ( (p2-p1) ^ (p4-p1) ) ) <= 0 &&

    sign( ( (p3-p4) ^ (p1-p4) ) * ( (p3-p4) ^ (p2-p4) ) ) <= 0; 

}

 

set < pair

set < vector

vector

vector

vector

TPoint P[N];

int Tc,n;

int Need;

int Ans;

int v[N];

 

bool Inside(TPoint p){

    int cnt=0;

    TPoint oth;

    oth.x=INF;

    oth.y=p.y;

    for (int i=0;i

        if ( On_Seg(p,P[Path[i]],P[Path[i+1]]) ) return false;

    for (int i=0;i

        TPoint A=P[Path[i]];

        TPoint B=P[Path[i+1]];

        if (A.y

        if (sign(A.y-B.y)==0) continue;

        if (sign(p.y-A.y)==0) continue;

        if (Seg_Cross(p,oth,A,B))

            cnt++;

    }

    return cnt&1;

}

 

int check(){

    if (Path.size()<4) return 0;

    T_path.clear();

    for (int i=Path.size()-1;i>=0;i–)

      T_path.push_back(Path[i]);

    if (Path_Hash.count(T_path)) return 0;

    for (int i=1;i<=n;i++) v[i]=0;

    for (int i=0;i

      v[Path[i]]=1;

    for (int i=1;i<=n;i++)

      if (!v[i])

        if (Inside(P[i])) return 0;

    return 1;

}

 

void dfs(int st,int z,int x,int Len){

    if (Len>Need) return;

    if (x==st){

        if (Len==Need && check()){

            Ans++;

            Path_Hash.insert(Path);

        }

        return;

    }

    int best=-1;

    double best_angle=-INF;

    for (int i=0;i

        int y=G[x][i];

        int s=sign( (P[x]-P[z])^(P[y]-P[z]) );

        double angle=0;

        if (!( s==0 && sign( (P[x]-P[z])*(P[y]-P[x]) )<0 )){

            if (s < 0){

                angle=Get_Angle(P[z]-P[x],P[y]-P[x]);

            }

            if (s > 0){

                angle=2*pi-Get_Angle(P[z]-P[x],P[y]-P[x]);

            }

            if (s == 0){

                angle=pi;

            }

            if (angle>best_angle){

                best_angle=angle;

                best=y;

            }

        }

    }

    if (best==-1) return;

    int y=best;

    if (Hash.count(make_pair(x,y))) return;

    Hash.insert(make_pair(x,y));

    Path.push_back(y);

    dfs(st,x,y,Len+1);

}

 

void solve(){

    Hash.clear();

    Path_Hash.clear();

    Ans=0;

    int i,j;

    for (i=1;i<=n;i++){

        for (j=0;j

            int x=i;

            int y=G[i][j];

            if (Hash.count(make_pair(x,y))) continue;

            Hash.insert(make_pair(x,y));

            Path.clear();

            Path.push_back(x);

            Path.push_back(y);

            dfs(x,x,y,1);

        }

    }

}

 

int main(){

    scanf("%d",&Tc);

    while (Tc–){

        scanf("%d",&n);

        for (int i=0;i<=n;i++) G[i].clear();

        for (int i=0;i

            int x,num;

            scanf("%d",&x);

            scanf("%lf%lf%d",&P[x].x,&P[x].y,&num);

            for (int j=0;j

                int y;

                scanf("%d",&y);

                G[x].push_back(y);

            }

        }

        scanf("%d",&Need);

        solve();

        printf("%dn",Ans);

    }

}