昨天比赛做到这道题,因为把题目理解错了,这道题怎么改都不对QAQ 正确理解题意是做对题的第一步,题目中有很多坑做的时候请小心避让。
题意:给你一个2到10的数,给出4n+1个坐标,判断是否在正方形的边上,每条边确保有n个点。(有且仅有一个点在在正方形内或正方形外)
(一开始用样例理解题意,认为边长是n+1所以全盘皆输了)
思路:找到平行x和y轴上最大和最小的边的位置,再进行逐一判断。数据量不大,可暴力。
1 #include<iostream> 2 #include<string> 3 #include<sstream> 4 #include<set> 5 #include<vector> 6 #include<map> 7 #include<algorithm> 8 #include<stdlib.h> 9 #include<cstdio> 10 #include<math.h> 11 #define ll long long 12 #define MOD 998244353 13 #define INF 0x3f3f3f3f 14 #define mem(a,x) memset(a,x,sizeof(a)) 15 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 16 using namespace std; 17 const int N = 110; 18 19 struct node 20 { 21 int x,y; 22 int flag; 23 } no[N]; 24 25 int main() 26 { 27 int n,mi1,mi2,ma1,ma2; 28 int a[N],b[N]; 29 scanf("%d",&n); 30 for(int i = 0; i < 4 * n + 1; i ++) 31 { 32 scanf("%d%d",&no[i].x,&no[i].y); 33 a[i] = no[i].x; 34 b[i] = no[i].y; 35 } 36 sort(a,a+4*n+1); 37 sort(b,b+4*n+1); 38 /* 39 判断最小值和最大值的这个地方需要注意注意再注意 40 不可以把第一个当作最小的,把最后一个当作最大的,会有特判样例 41 由于每条边上至少有n个点,只有一个点是不在边上的, 42 所以第二个一定是最小的,倒数第二个一定是最大的 43 */ 44 mi1=a[1]; 45 ma1=a[4*n-1]; 46 mi2=b[1]; 47 ma2=b[4*n-1]; 48 //cout<<ma1<<' '<<mi1<<endl; 49 //cout<<ma2<<' '<<mi2<<endl; 50 for(int i = 0; i < 4 * n + 1; i ++) 51 { 52 if((no[i].x>mi1&&no[i].x<ma1&&no[i].y>mi2&&no[i].y<ma2)||no[i].x<mi1||no[i].x>ma1||no[i].y<mi2||no[i].y>ma2) 53 { 54 printf("%d %d\n",no[i].x,no[i].y); 55 break; 56 } 57 } 58 return 0; 59 }