题目链接: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 }