CodeForces - 1184C1 Heidi and the Turing Test (Easy)

昨天比赛做到这道题,因为把题目理解错了,这道题怎么改都不对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 }

 

上一篇:构造图灵机Turing


下一篇:NVIDIA Turing Architecture架构设计(下)