奇迹之流WonderfloW

Nothing Replaces Hard Work!

ZOJ1299 Pendulum && ZOJ1041 && ZOJ1060 && ZOJ1197

| Comments

zoj1299《Pendulum》是个恶心的模拟题,也可以说是个计算几何题,就是模拟一根绳子摆动的过程,中间可能会碰到障碍物导致圆心改变等等。自己写不好,只好学学大神的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <cmath>
#include <cstdio>

const double EPS = 1e-4;
const int MAXN = 512;

//小于
inline bool lt(double a, double b) {
  return a < b - EPS;
}

//大于
inline bool gt(double a, double b) {
  return a > b + EPS;
}

//等于
inline bool eq(double a, double b) {
  return fabs(a - b) < EPS;
}

int main() {
  int ri = 0, n, p, q;
  bool flag;
  double t, r, dr, tr, alpha, beta, gamma;
  //alpha:当前悬线所在弧度
  //beta:当前对比过程中选出的顺时针距当前悬线最近的
  //gamma:当前对比过程中第i个的弧度
  double x[MAXN], y[MAXN];//所有点都存进来

  while (scanf("%d%lf", &n, &r) != EOF && r > 0) {
      x[0] = y[0] = 0;
      p = 0;
      alpha = -M_PI; 
      //M_PI = acos(-1.0) 区别是这个M_PI是头文件里定义好的
      for (int i = 1; i <= n; ++i) {
          scanf("%lf%lf", &x[i], &y[i]);
      }

      t = 0;
      while (true) {
          q = -1;
          for (int i = 1; i <= n; ++i) {
              if (i == p) {       //p是当前所在弧的中心,一开始就是(0,0)
                  continue;
              }
              tr = hypot(y[i] - y[p], x[i] - x[p]);
              //hypot函数用于两直角边求斜边长
              gamma = atan2(y[i] - y[p], x[i] - x[p]);
              //atan2函数求由x轴到当前点的角度
              if (!lt(tr, r)) {
                  //如果长度不够碰到点
                  continue;
              }
              flag = false;
              if (q == -1) {
                  flag = true;    // !eq(gamma, alpha);
              } else if (eq(gamma, beta)) {
                  //两个点相对于原点的弧度值相同,那么取长度长的
                  //显然两个都碰到后,产生的效果就是碰到长的时的效果
                  flag = gt(tr, dr);
              } else if (lt(gamma, alpha)) {
                  //beta如果在悬线右边肯定就pass了。因为是顺时针转的
                  //当前弧度在悬线左边,就要选出一个更左边的
                  flag = lt(beta, alpha) && lt(gamma, beta);
              } else if (gt(gamma, alpha)) {
                  //如果beta在左边,那么肯定用当前的换beta
                  //都在悬线右边,看哪个更小了
                  flag = lt(beta, alpha) || lt(gamma, beta);
              }
              if (flag) {
                  //算出当前轮悬线即将碰到的点是哪个,同时保留半径和弧度
                  q = i;
                  dr = tr;
                  beta = gamma;
              }
          }

          // valid beta?
          flag = false;
          //检查有没有可能开始来回荡
          if (gt(y[p] + r, 0)) {  // y[q] < 0 //势能不足够,可能出现来回荡的情况
              gamma = asin(-y[p] / r);
              if (q == -1 ||
                  (lt(alpha, gamma) && lt(gamma, beta)) ||
                  (gt(alpha, beta)/* && (gt(gamma, alpha) || lt(gamma, beta))*/)) {
                  //最靠近的那个距离都不够 ||
                  //最靠近的那个高度需要超过x轴才能碰到(势能不够)
                  q = -1;
                  beta = gamma;
                  flag = true;
              }
          }
          if (q != -1 || flag) {
              if (lt(alpha, beta)) {
                  t += r * (beta - alpha);
              } else if (lt(beta, alpha)) {   // !!
                  t += r * (beta - alpha + 2 * M_PI);
              } else {
                  // t += 0;
              }
              //加上那段弧
          }
          if (q != -1) {
              //表示本轮找到了可以相碰的点,碰撞后继续
              p = q;
              r -= dr;
              alpha = beta;
              continue;
          }

          printf("Pendulum #%d\nLength of periodic orbit = ", ++ri);
          printf("%.2lf\n\n", flag ? 2 * t : 2 * M_PI * r);
          break;
      }
  }
  return 0;
}
// TEST CASE
// 3 27.0
// 0 -12
// 3 -8
// 6 -4

zoj1041《Transmitters》是个计算几何,计算半圆最多覆盖平面上点的个数,只要暴力枚举每个点为半圆的起点,看左右两边的半圆各能覆盖多少个点,然后比较出一根最大值就可以了。N2的复杂度就能过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std;
#define EPS 10e-5
struct Point
{
  double x,y;
}p[200],o;
double d;
double a,b;

int n,num;

bool calcDis(double a,double b)
{
  double dis = (o.x-a)*(o.x-a)+(o.y-b)*(o.y-b);
  if(dis>d*d)return false;
  return true;
}

double xmult(Point a,Point b)
{
  return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}

int main()
{
  while(scanf("%lf%lf%lf",&o.x,&o.y,&d)!=EOF)
  {
      if(d<0)break;
      num = 0;
      scanf("%d",&n);
      for(int i=0;i<n;i++)
      {
          scanf("%lf%lf",&a,&b);
          if(calcDis(a,b))
          {
              p[num].x = a;
              p[num++].y = b;
          }
      }
      int ans = 0;
      for(int i=0;i<num;i++)
      {
          int d1,d2;
          d1 = d2 = 0;
          for(int j=0;j<num;j++)
          {
              if(i==j)continue;
              double dis = xmult(p[i],p[j]);
              if(fabs(dis)<EPS){d1++;d2++;}
              else if(dis<0){d1++;}
              else {d2++;}
          }
          ans = max(ans,d1+1);
          ans = max(ans,d2+1);
      }
      printf("%d\n",ans);

  }

  return 0;
}

zoj1060 《Sorting It All Out》是一个拓扑排序的题,需要注意的是,如果前面排出了n个点的顺序,哪怕后面又出现了不一致,也要当做排出了顺序来输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<memory.h>
using namespace std;
int n,m;
vector<int>edge[50];
queue<int>myque;
char str[10];
int deg[50];
int dd[50];
bool vis[50];
bool com[50];
bool inc;
int ans[50];
int anum = 0;

void dfs(int v)
{
  vis[v] = true;
  for(int i=0;i<edge[v].size();i++)
  {
      int a = edge[v][i];
      if(vis[a]){inc = true; return;}
      else dfs(a);
  }
}

int top_sort(int acase)
{
  while(!myque.empty())myque.pop();
  int pnum = 0;
  for(int i=0;i<=n;i++)
  {
      if(com[i]&&!dd[i])
      {
          myque.push(i);
          pnum++;
      }
  }
  int index;
  anum = 0;
  bool fa = false;
  while(!myque.empty())
  {
      if(pnum>1){fa = true;}
      pnum = 0;
      index = myque.front();
      ans[anum++] = index;
      myque.pop();
      for(int i=0;i<edge[index].size();i++)
      {
          dd[edge[index][i]]--;
          if(!dd[edge[index][i]])
          {
              pnum++;
              myque.push(edge[index][i]);
          }
      }
  }
  if(anum==n&&!fa)return 1;
  if(anum<acase)return -1;
  return 0;
}

int main()
{
//    freopen("in.txt","r",stdin);
  while(scanf("%d%d",&n,&m)!=EOF)
  {
      if(n+m==0)break;
      for(int i=0;i<=n;i++)
      {
          com[i] = false;
          deg[i] = 0;
          edge[i].clear();
      }
      int ok = 0;
      int num = -1;
      int upnum = 0;
      for(int i=0;i<m;i++)
      {
          scanf("%s",str);
          edge[str[0]-'A'].push_back(str[2]-'A');
          deg[str[2]-'A']++;
          if(!com[str[0]-'A'])
          {
              upnum++;
              com[str[0]-'A'] = true;
          }
          if(!com[str[2]-'A'])
          {
              com[str[2]-'A'] = true;
              upnum++;
          }
          if(!ok)
          {
              for(int j=0;j<=n;j++)
              {
                  dd[j] = deg[j];
              }
              ok = top_sort(upnum);
              num = i+1;
          }
      }
      switch(ok)
      {
          case 0:
              printf("Sorted sequence cannot be determined.\n");
              break;
          case -1:
              printf("Inconsistency found after %d relations.\n",num);
              break;
          default:
              printf("Sorted sequence determined after %d relations: ",num);
              for(int i=0;i<anum;i++)printf("%c",ans[i]+'A');
              printf(".\n");
              break;
      }
  }

  return 0;
}

zoj1197 《Sorting Slides》是:N个透明的矩形框和N个点,分别找出N个点所对应的矩形框是哪个。可以拓扑排序,可以匹配。 不过我拓扑排序wa到死,写了三遍还是wa,最后放弃了。改用二分图的匹配。只要枚举每条边去掉后看匹配数是不是N-1,如果是,那么代表这就是方案的一条边,如果整个过程中找到了两条以上,那么明显又出现了矛盾,输出none,否则算到答案里面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 30

bool MaxMatchDFS(bool g[][maxn], int m, int a, int y[], bool u[])
{
    for (int i=0; i<m; i++)
        if (!u[i] && g[a][i])
        {
            int t=y[i];
            u[i]=true; y[i]=a;
            if (t==-1 || MaxMatchDFS(g, m, t, y, u)) return true;
            y[i]=t;
        }
    return false;
}
int MaxMatch(bool g[][maxn], int n, int m) //v1[y[i]] matches v2[i]
{
    int y[maxn];
    memset(y, 255, sizeof(y));
    int c=0;
    for (int i=0; i<n; i++)
    {
        bool u[maxn]={0};
        if (MaxMatchDFS(g, m, i, y, u)) c++;
    }
    return c;
}

bool init(bool g[][maxn], int &n)
{
    int xmin[maxn], xmax[maxn], ymin[maxn], ymax[maxn];
    int x[maxn], y[maxn];
    scanf("%d", &n);
    if (n==0) return false;
    for (int i=0; i<n; i++)
        scanf("%d%d%d%d", &xmin[i], &xmax[i], &ymin[i], &ymax[i]);
    for (int i=0; i<n; i++)
        scanf("%d%d", &x[i], &y[i]);
    memset(g, false, sizeof(*g)*maxn);
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
        {
            if (xmin[i]<x[j] && xmax[i]>x[j]
                && ymin[i]<y[j] && ymax[i]>y[j])
            g[i][j]=1;
        }
    return true;
}

int main()
{
    int cs=0;
    int n, unique, match; 
    bool g[maxn][maxn];
    bool found;
    while (init(g, n))
    {
        found=false;
        printf("Heap %d\n", ++cs);
        for (int i=0; i<n; i++)
        {
            unique=-1;          //0:false 1:true -1:not sure
            match=-1;
            for (int j=0; j<n; j++)
                if (g[i][j])
                {
                    g[i][j]=false;
                  //cut an edge and try whether it's a right match
                    if (MaxMatch(g, n, n)==n-1)
                    {
                        if (unique==-1){unique=1;match=j;}
                        else {unique=0; break;} 
                    }
                    g[i][j]=true;
                }
            if (unique==1)
            {
                if (found==false) found=true;
                else printf(" ");
                printf("(%c,%d)", i+'A', match+1);
            }
        }
        if (found==false) printf("none\n\n");
        else printf("\n\n");
    }
    return 0;
}