题目描述
某一天你要去看满月, 但是你发觉月亮只能看到一部分。
现在你看到这些部分全部抽象成平面上的点, 并且这些点只可能是在月亮的中心或者是月亮的边缘上。
现在问你, 月亮可能在什么位置上(就是哪个点可以做月亮的中心)。
输入
第一行一个整数N,表示有多少个点。(N<1000)
下面N行每行两个实数,表示点的坐标。
输出
一行一个整数, 表示读入中的第几个点。
样例输入
5 0 0 3 4 4 3 -3 4 -4 3
样例输出
1
本题的题意比较简单,就是要求出月亮中心的点可能是哪个,刚开始做的时候也是有点不知所措,以为是什么二分之类的,后来发现可以用暴力的方法来解决问题
用一个结构体,里面有两个变量,标志着个点的横纵坐标,然后用dis函数来求解两个点之间的距离
开始想将求出来的两点间的的距离放在数组里,之后定义一个flag变量来判断是否里面的距离都是相等的,如果是相等的,那么上面for循环这个i的大小就是答案,后来发发现这至少三层 for 复杂度有点高,然后放弃了这种做法
=>=> 关键点:于是乎我就判断没两个相邻的求出的距离是否相等,如果相邻的两个距离都不想等,那么这个点一定不是月亮的中心,如果每次和之前的距离进行比较,没有发现不同,那么这个点就一定是月亮的中心
对于以上所述,比较两点之间的距离的时候,这个点和本身不是同一个点,换句话说不用求解自己到自己的距离,会干扰答案
#pragma GCC optimize (2) #pragma G++ optimize (2) #include <bits/stdc++.h> #include <algorithm> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define wuyt main typedef long long ll; #define HEAP(...) priority_queue<__VA_ARGS__ > #define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > template<class T> inline T min(T &x,const T &y){return x>y?y:x;} template<class T> inline T max(T &x,const T &y){return x<y?y:x;} //#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) //char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf; ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar(); if(c == '-')Nig = -1,c = getchar(); while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar(); return Nig*x;} #define read read() const ll inf = 1e15; const int maxn = 2e5 + 7; const int mod = 1e9 + 7; #define start int wuyt() #define end return 0 struct node { int x,y; }; double dis(int x1,int y1,int x2,int y2){ return (double)sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } double num[10000]; start{ int n=read; node cnt[n+1]; for(int i=1;i<=n;i++) { cnt[i].x=read; cnt[i].y=read; } for(int i=1;i<=n;i++){ int flag=1;int ct=1; for(int j=1;j<=n;j++){ if(i!=j){ num[ct]=dis(cnt[i].x,cnt[i].y,cnt[j].x,cnt[j].y); num[0]=num[1]; if(num[ct]!=num[ct-1]){ flag=0; break; } ct++; } if(flag==0) break; if(flag==1&&j==n){ printf("%d\n",i); return 0; } } } end; } /************************************************************** Language: C++ Result: 正确 Time:1 ms Memory:2100 kb ****************************************************************/