2012 MUTC 9 总结

题解链接：http://page.renren.com/601081183/note/866929096

　　这次的比赛打得相当不好，只过了一道题，那道题还是在不求甚解的情况下过的。

　　这次暴露出很多缺陷，例如对奇偶性的理解不透彻，对数位统计相当不熟悉，组队的配合不稳定，这次配合显然差了很多！水题的代码就不贴了，其他题的会逐题添加！

1001(hdu 4380)：

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 
 5 using namespace std;
 6 const int maxn = 101;
 7 const double eps = 1e-6;
 8 
 9 struct point{
10     double x;
11     double y;
12 }house[maxn], gold[1001];
13 bool odd[maxn][maxn];
14 
15 double area(point a, point b, point c){
16     return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
17 } // 计算叉积
18 
19 bool in_tri(point p, point a, point b, point c){
20     double tri = fabs(area(a, b, c));
21     double tmp = fabs(area(a, b, p)) + fabs(area(b, c, p)) + fabs(area(c, a, p));
22 
23     //printf("%.2f %.2f\n", tri, tmp);
24     return fabs(tri - tmp) < eps && fabs(tri) > eps;
25 } // 用叉积求面积来判断点是否在三角形内
26 
27 void make_line(int n, int m){
28     point centre;
29 
30     centre = house[0];
31     for (int i = 0; i < n; i++){
32         for (int j = i + 1; j < n; j++){
33             odd[i][j] = 0;
34             for (int k = 0; k < m; k++){
35                 if (in_tri(gold[k], centre, house[i], house[j])){
36                     odd[i][j] = !odd[i][j];
37                     //printf("%d %d: %d\n", i, j, odd[i][j]);
38                 }
39             }
40         }
41     }
42 } // 每两个点和基准点形成三角形，而不是题解里面说的原点，统计三角形内点的奇偶性
43 
44 int make_tri(int n){
45     int cnt;
46 
47     cnt = 0;
48     for (int i = 0; i < n; i++){
49         for (int j = i + 1; j < n; j++){
50             for (int k = j + 1; k < n; k++){
51                 if (odd[i][j] ^ odd[j][k] ^ odd[i][k])
52                     cnt++;
53             }
54         }
55     }
56 
57     return cnt;
58 } // 利用每两个点与基准点形成的三角形中点的个数的奇偶性来判断所形成的新三角形中点的个数的奇偶性
59 
60 void deal(int n, int m, int cc){
61     memset(house, 0, sizeof(house));
62     memset(gold, 0, sizeof(gold));
63     memset(odd, 0, sizeof(odd));
64     for (int i = 0; i < n; i++){
65         scanf("%lf%lf", &house[i].x, &house[i].y);
66     }
67     for (int i = 0; i < m; i++){
68         scanf("%lf%lf", &gold[i].x, &gold[i].y);
69     }
70     make_line(n, m);
71     printf("Case %d: %d\n", cc, make_tri(n));
72 }
73 
74 int main(){
75 #ifndef ONLINE_JUDGE
76     freopen("in", "r", stdin);
77 #endif
78     int n, m;
79     int T = 1;
80 
81     while (~scanf("%d%d", &n, &m)){
82         deal(n, m, T);
83         T++;
84     }
85 
86     return 0;
87 }

　　目标：练就强硬的外壳——模拟，学精代码的灵魂——算法！

——written by Lyon