F题:Dot the i's and Cross the T's

题目链接:https://nanti.jisuanke.com/t/43317

题目大意:

给出n组数据,每组数据有p个点,找出每组能够符合题目中要求的 ' T ' 型的个数。

思路:

 

 首先通过枚举A,B两点,再遍历寻找符合条件的M(M为线段AB的中点),找到符合条件的M点时再遍历一遍寻找C点(  |CM| = |AB|  )。

解题代码:

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <string>
 6 #include <cstring>
 7 #include <map>
 8 using namespace std;
 9 const long long N = 1e9 + 7;
10 typedef long long ll;
11 struct point
12 {
13     double x;
14     double y;
15 
16 }p[55];
17 bool sign(double z)
18 {
19     if(fabs(z) < 1e-6)
20         return true;
21     else
22         return false;
23 }
24 
25 int main()
26 {
27     int t;
28     double x1,y1,x2,y2;
29     cin >> t;
30     for(int i = 1;i <= t;i++)
31     {
32         int n;
33         ll num = 0;
34         cin >> n;
35         for(int j = 0;j < n;j++)
36             cin >> p[j].x >> p[j].y;
37         for(int j = 0;j < n-1;j++)
38         {
39             for(int k = j+1;k < n;k++)
40             {
41                 for(int l = 0;l < n;l++)
42                 {
43                     if(l == j || l == k)
44                         continue;
45                     if( sign( (p[j].x+p[k].x) - p[l].x *2) && sign( (p[j].y+p[k].y)  - p[l].y*2 ) )
46                     {
47 
48                         for(int h = 0;h < n;h++)
49                         {
50                             if(h == j || h == k || h == l)
51                                 continue;
52                             x1 = p[j].x - p[k].x;
53                             y1 = p[j].y - p[k].y;
54                             x2 = p[l].x - p[h].x;
55                             y2 = p[l].y - p[h].y;
56 
57                             if( sign(x1*x2 + y1*y2) &&  sign( hypot(p[l].y-p[h].y , p[l].x - p[h].x) - hypot(p[j].y-p[k].y , p[j].x - p[k].x) ) )
58                             {
59                                 num++;
60 
61                             }
62 
63                         }
64 
65                     }
66 
67                 }
68             }
69 
70         }
71         printf("Set #%d: %lld\n\n",i,num);
72 
73 
74     }
75     return 0;
76 }