USACO 3.4

3.4开始的TEXT介绍的是比较常用的计算几何知识，没有细看。计算几何就是把平时的几何学问题用编程解决的技术，例如给两点坐标求过两点的直线方程等。现实中很容易写出一些式子，但是在计算机中因为分母为0（这样如果用y = kx+b表示直线的话，垂直的直线斜率是无穷大）之类的问题所以会显得稍微复杂一点。计算几何也是ACM中代码量相当大的一类。

这节题目比较少，只有4题，而且除了第一题计算几何以外代码量都不大。因此只要过了第一题，就算是过了一半了。

Closed Fences：不愧是计算几何，本节最难搞的题。感谢可可帮我拍代码，教我判断点在线段上和给两个线段的端点求交点的技巧。题目分成2部分，第一部分判断栅栏是否合法，第二部分求看到的栅栏都是哪些。因为数据量比较小，第一部分直接O(n^2)判是否有线段相交就可以了。第二部分只要把所有的点进行极角排序，然后对相邻两个角度取平均数（注意有可能相邻角度是一样的，这时候要跳过），作对应平均角度的射线，看和哪些线段相交，然后取交点离视点最近的那一条设为能被看见。注意线段输出顺序。

  1 # include <stdio.h>
  2 # include <math.h>
  3 # include <stdlib.h>
  4 # include <string.h>
  5 
  6 
  7 #define SEGMENT(x) vx[x],vy[x],vx[x+1],vy[x+1]
  8 
  9 
 10 int n, ox, oy, vx[220], vy[220], can_be_see[220] ;
 11 double angle[220] ;
 12 double pi = acos(-1.0) ;
 13 
 14 
 15 double cross_product(double x, double y, double xx, double yy){return x*yy-y*xx;}
 16 int in_rect(double l, double t, double r, double b, double x, double y)
 17 {
 18     return ((x>=l&&x<=r)||(x>=r&&x<=l)) && ((y>=t&&y<=b)||(y>=b&&y<=t)) ; 
 19 }
 20 
 21 
 22 int intersection(    double sx1, double sy1, double ex1, double ey1,
 23                     double sx2, double sy2, double ex2, double ey2)
 24 {
 25     double     d1 = cross_product(ex1-sx1, ey1-sy1, sx2-sx1, sy2-sy1), 
 26             d2 = cross_product(ex1-sx1, ey1-sy1, ex2-sx1, ey2-sy1), 
 27             d3 = cross_product(ex2-sx2, ey2-sy2, sx1-sx2, sy1-sy2), 
 28             d4 = cross_product(ex2-sx2, ey2-sy2, ex1-sx2, ey1-sy2) ;
 29     
 30     if (d1*d2 < 0 && d3*d4 < 0) return 1 ;
 31     if (d1==0 && in_rect(sx1,sy1,ex1,ey1,sx2,sy2)) return 1 ;
 32     if (d2==0 && in_rect(sx1,sy1,ex1,ey1,ex2,ey2)) return 1 ;
 33     if (d3==0 && in_rect(sx2,sy2,ex2,ey2,sx1,sy1)) return 1 ;
 34     if (d4==0 && in_rect(sx2,sy2,ex2,ey2,ex1,ey1)) return 1 ;
 35     return 0 ;
 36 }
 37 
 38 
 39 int parallel(        double sx1, double sy1, double ex1, double ey1,
 40                     double sx2, double sy2, double ex2, double ey2)
 41 {
 42     return (((ex1-sx1)*(ey2-sy2) - (ex2-sx2)*(ey1-sy1)) == 0) ;
 43 }
 44 
 45 
 46 int get_point (        double sx1, double sy1, double ex1, double ey1,
 47                     double sx2, double sy2, double ex2, double ey2,
 48                     double* px, double* py)
 49 {
 50     if (parallel(sx1, sy1, ex1, ey1, sx2, sy2, ex2, ey2)) return 0 ;
 51     if (!intersection(sx1, sy1, ex1, ey1, sx2, sy2, ex2, ey2)) return 0 ;
 52     double A1 = ey1 - sy1, B1 = sx1 - ex1, C1 = A1*sx1 + B1*sy1 ;
 53     double A2 = ey2 - sy2, B2 = sx2 - ex2, C2 = A2*sx2 + B2*sy2 ;
 54     double det = A1*B2 - A2*B1;
 55     if (det == 0) return 0 ;
 56     *px = (B2*C1 - B1*C2)/det;
 57      *py = (A1*C2 - A2*C1)/det;
 58      return 1 ;
 59 }
 60 
 61 
 62 int valid()
 63 {
 64     int i, j ;
 65     for (i = 0 ; i < n; i++)
 66         for (j = i+2 ; j < n; j++)
 67         {
 68             if (i==0 && j == n-1) continue ;
 69             if (intersection(SEGMENT(i), SEGMENT(j)))
 70                 return 0 ;
 71         }
 72     return 1 ;
 73 }
 74 
 75 
 76 int cmp(const void *a, const void *b)
 77 {
 78     double p = *(double*)a , q = *(double*)b ;
 79     if (p < q) return -1 ;
 80     if (p > q) return 1 ;
 81     return 0 ;
 82 }
 83 
 84 
 85 int test(double ang)
 86 {
 87     double ex = 1e5*cos(ang), ey = 1e5*sin(ang), dist = 1e9 ;
 88     double d, px, py ;
 89     int idx = -1, i ;
 90     for (i = 0 ; i < n ; i++)
 91         if (get_point(0,0,ex,ey, SEGMENT(i), &px, &py))
 92         {
 93             d = px*px + py*py ;
 94             if (idx == -1 || d < dist) dist = d, idx = i ;
 95         }
 96     can_be_see[idx] = 1 ;
 97 }
 98 
 99 
100 void watch()
101 {
102     int i, num = 0 ;
103     for (i = 0 ; i < n ; i++)
104         angle[i] = atan2(vy[i], vx[i]) ;
105     qsort(angle, n, sizeof(angle[0]), cmp) ;
106     angle[n] = angle[0]+2*pi ;
107     memset (can_be_see, 0, sizeof(can_be_see)) ;
108     for (i = 0 ; i < n ; i++) if (angle[i]!= angle[i+1])
109         test((angle[i]+angle[i+1])/2.0) ;
110     for (i = 0 ; i < n ; i++) num += can_be_see[i] ;
111     printf ("%d
", num) ;
112     for (i = 0 ; i < n -2  ; i++)
113         if (can_be_see[i])
114             printf ("%d %d %d %d
", vx[i]+ox, vy[i]+oy, vx[i+1]+ox, vy[i+1]+oy) ;
115     if (can_be_see[n-1])
116         printf ("%d %d %d %d
", vx[0]+ox, vy[0]+oy, vx[n-1]+ox, vy[n-1]+oy) ;
117     if (can_be_see[n-2])
118         printf ("%d %d %d %d
", vx[n-2]+ox, vy[n-2]+oy, vx[n-1]+ox, vy[n-1]+oy) ;
119 }
120 
121 
122 void work()
123 {
124     if (!valid ())
125         puts("NOFENCE") ;
126     else
127         watch() ;
128 }
129 
130 
131 int main ()
132 {
133     int i ;
134     freopen ("fence4.in", "r", stdin) ;
135     freopen ("fence4.out", "w", stdout) ;
136     while (~scanf ("%d", &n))
137     {
138         scanf ("%d%d", &ox, &oy) ;
139         for (i = 0 ; i < n ; i++)
140             scanf ("%d%d", &vx[i], &vy[i]), vx[i]-=ox, vy[i]-=oy ;
141         vx[n] = vx[0], vy[n] = vy[0] ;
142         work() ;
143     }
144     return 0 ;
145 }

View Code

American Heritage：给二叉树的中序和先序遍历结果，求后序遍历。非常基础的数据结构题。只要想清楚递归的策略，写起来很简单。

 1 # include <stdio.h>
 2 # include <string.h>
 3 
 4 
 5 char in[30], pre[30] ;
 6 
 7 
 8 void gao(int in_s, int in_e, int pre_s, int pre_e)
 9 {
10     int i, left_num, right_num ;
11     for (i = in_s ; i <= in_e ; i++)
12         if (in[i]==pre[pre_s]) break ;
13     left_num = i-in_s, right_num = in_e-i ;
14     if (left_num) gao(in_s, i-1, pre_s+1, pre_s+left_num) ;
15     if (right_num) gao(i+1, in_e, pre_e - right_num+1, pre_e) ;
16     printf ("%c", pre[pre_s]) ;
17 }
18 
19 
20 int main ()
21 {
22     freopen ("heritage.in", "r", stdin) ;
23     freopen ("heritage.out", "w", stdout) ;
24     while (~scanf ("%s%s", in, pre))
25     {
26         gao(0, strlen(in)-1, 0, strlen(in)-1) ;
27         puts("") ;
28     }
29     return 0 ;
30 }

View Code

Electric Fence：这题只要知道皮克公式，就能非常轻松地解决。注意的是线段上点的数量是线段纵横坐标差的最大公约数加1。三角形三边分别求边上的点数后加起来作为整个图形的边上点数，此时3个顶点被加了2次，要减回。

 1 # include <stdio.h>
 2 
 3 
 4 int myabs(int x){return x<0?-x:x;}
 5 int gcd(int a, int b){return a%b?gcd(b,a%b):b;}
 6 int count(int a, int b){return 1+(!b ? a : gcd(a,b));}
 7 
 8 
 9 int main ()
10 {
11     int n, m, p ;
12     freopen ("fence9.in", "r", stdin) ;
13     freopen ("fence9.out", "w", stdout) ;
14     while (~scanf ("%d%d%d", &n, &m, &p))
15     {
16         double area = m*p*0.5 ;
17         double edge_number = count(n,m) + count(p,0) + count(myabs(n-p),m) - 3 ;
18         printf ("%.0lf
", area+1-edge_number*0.5) ;
19     }
20     return 0 ;
21 }

View Code

Raucous Rockers：有点诡异的dp题。因为数据量很小，才20，若不是可可找我讨论这题，我肯定直接暴力了。若把唱片和分钟数排列成一排，则可以看成一个01背包问题。只不过对于第i首歌，假设时间是t[i]，要注意每首唱片开始前的i-1分钟内的点是不能用01背包的方程进行转移的。这题的数据非常非常弱，一开始写了一个错的dp，结果A了，通不过这组数据（我输出2，其实是3）：

4 3 1

1 1 1 2

可见这题的数据有多弱……

 1 # include <stdio.h>
 2 # include <string.h>
 3 
 4 
 5 int dp[500] ;
 6 
 7 
 8 int main ()
 9 {
10     int n, t, m ;
11     int i, j, k, a ;
12     freopen ("rockers.in", "r", stdin) ;
13     freopen ("rockers.out", "w", stdout) ;
14     while (~scanf ("%d%d%d", &n, &t, &m))
15     {
16         memset(dp, 0, sizeof(dp)) ;
17         for (i = 0 ; i < n; i++)
18         {
19             scanf ("%d", &a) ;
20             if (a > t) continue ;
21             for (j = m-1 ; j >= 0 ; j--)
22                 for (k = t ; k >= a; k--)
23                     if (dp[j*t+k] < dp[j*t+k-a] + 1)
24                         dp[j*t+k] = dp[j*t+k-a] + 1 ;
25             for (j = 1 ; j <= m*t ; j++)
26                 if (dp[j]<dp[j-1])dp[j] = dp[j-1] ;
27         }
28         printf ("%d
", dp[m*t]) ;
29     }
30     return 0 ;
31 }

View Code

至此终于是写完了第三章，写了那么久，有点逗……