[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);

    }

}

[ZOJ1021 The Willy Memorial Program]【狗狗40题】【特别特别坑爹】

规模十分之小,但是特别特别坑T_T

一定要看清楚这一段话:

As an example, if we set the target point to level 4 in the left pipe in the figure above, the elapsed time for water to reach that target is assumed to be 5 (not 2), Also note that if the water reaches to the top of a pipe (say in level x), it won't pour out outside the pipe until empty spaces in connected pipes below level x are filled (if can be filled, i.e. the level of water reaches the connecting links). (Note that there may be some links at level x, to which water is entered). After all such spaces are filled; the water level would not go up further.

然后别的怎么暴力都0MS……

搜狗V5啊,在学校上不了ZOJ,用了搜狗的全网加速就上得了啦……其实就是个代理T_T

const int N=55;
const int INF=0x7FFFFFFF;
int n,m,Target_i,Target_level;
struct Pipe{int x,y,h;}P[N];
struct Link{int p1,p2,y;}L[N];
int level[N];

void gao(){
    int i,j,k,ans=0;
    fill(level,level+n+1,INF);
    level[1]=P[1].y+P[1].h;
    while (1){ //退出条件:1、满了 2、达到target
        for (i=1;i<=n;i++)
          for (j=1;j<=n;j++)
            for (k=1;k<=m;k++)if (L[k].p1==j || L[k].p2==j){
              int x,y;
              if (L[k].p1==j) { x=L[k].p2; y=j; }
                         else { x=L[k].p1; y=j; }
              if (level[x]==INF && level[y]==L[k].y) level[x]=P[x].y+P[x].h;
            }
        int cnt=0,Max=-INF;
        bool check=true;
        for (i=1;i<=n;i++)
          if (level[i]!=INF && level[i]>Max)
              Max=level[i];
        for (i=1;i<=n;i++)
          if (level[i]!=INF && level[i]==Max)
            if (level[i]>P[i].y){
              cnt++;
              level[i]--;
            }
            elseif (level[i]==P[i].y)
              check=false;
        if (!check) cnt=0;
        if (cnt==0){
            puts("No Solution");
            return;
        }
        if (level[Target_i]            cout << ans << endl;
            return;
        }
        ans+=cnt;
    }
}

void add(int k,int x,int y,int l){
    int p1=0,p2=0;
    for (int i=1;i<=n;i++){
      if (y>=P[i].y && y<=P[i].y+P[i].h && P[i].x+1==x) p1=i;
      if (y>=P[i].y && y<=P[i].y+P[i].h && P[i].x==x+l) p2=i;
    }
    L[k].p1=p1;
    L[k].p2=p2;
    L[k].y=y;
}

int main(){
    int Tc,x,y,l;
    cin >> Tc;
    while (Tc--){
        cin >> n;
        for (int i=1;i<=n;i++) cin >> P[i].x >> P[i].y >> P[i].h;
        cin >> m;
        for (int i=1;i<=m;i++){
            cin >> x >> y >> l;
            add(i,x,y,l);
        }
        cin >> Target_i >> Target_level;
        if (Target_level<=P[Target_i].y || Target_level>P[Target_i].y+P[Target_i].h)
            puts("No Solution");
        else
            gao();
    }
}

一些数据:

3

7
10 4 6
7 0 13
12 0 13
3 2 8
0 7 6
1 0 6
5 5 7
13
2 1 5
2 3 1
1 9 2
1 12 4
4 8 1
11 10 1
8 13 4
8 2 4
4 4 3
8 5 2
4 6 1
6 7 1
6 11 1
7 12

3
0 0 1
2 1 1
4 1 2
2
1 1 1
3 2 1
2 2

2
0 0 3
2 3 1
1
1 3 1
1 3