Python3(3.5.2) 解法, 执行用时: 1003ms, 内存消耗: 3716K, 提交时间: 2019-06-16 14:19:55

def dis(p, q):
    return ((p[0]-q[0])**2 + (p[1]-q[1])**2)

n = int(input())
l = []
for _ in range(n):
    l.append(tuple(map(int, input().split())))
fil = [1 for i in range(n)]
i = 0
while (sum(fil) > 1):
    while (fil[i] == 0):
        i += 1
        i = i%n
    dic = {}
    z = 0
    sl = n
    for j in range(n):
        if (j==i):
            continue
        if (fil[j]):
            di = dis(l[i], l[j])
            dic[j] = di
            if (sl == n):
                sl = j
                z = di
            if (di < z):
                sl = j
                z = di
    fil[sl] = 0
    i += 1
    i = i%n
i = 0
while (fil[i] == 0):
    i += 1
    i = i%n
print(i+1)

C++14(g++5.4) 解法, 执行用时: 6ms, 内存消耗: 492K, 提交时间: 2019-06-14 16:17:21

#include <iostream>
#include <stdio.h>
using namespace std;
int n,x[1010],y[1010],dead[1010];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
	int now=1;
	for(int i=1;i<n;i++)
	{
		while(dead[now]){now++;if(now>n) now-=n;} 
		int mindis=1<<30,id;
		for(int j=1;j<=n;j++)
		{
			if(j==now||dead[j]) continue;
			int dis=(x[now]-x[j])*(x[now]-x[j])+(y[now]-y[j])*(y[now]-y[j]);
			if(dis<mindis) mindis=dis,id=j;
		}
		//cout<<now<<"-->"<<id<<endl;
		dead[id]=1;
		now++;if(now>n) now-=n;
	}
	while(dead[now]){now++;if(now>n) now-=n;}
	printf("%d\n",now);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 484K, 提交时间: 2019-06-14 12:24:22

#include<stdio.h>
#define N 1005
int G[N][2];
int dis(int a,int b) {
	int x=G[a][0]-G[b][0],y=G[a][1]-G[b][1];
	return x*x+y*y;
}
int main() {
	int cur,n,i,j,live[N],out,mind,d;
	scanf("%d",&n);
	for(i=1;i<=n;i++) {
		live[i]=1;
		scanf("%d%d",&G[i][0],&G[i][1]);
	}
	for(cur=1,i=1;i<n-1;i++) {
		mind=0;
		for(j=1;j<=n;j++) {
			if(!live[j] || j==cur) continue;
			d=dis(cur,j);
			if(d<mind || !mind) {
				mind=d,
				out=j;
			}
		}
		live[out]=0;
		while(1) {
			cur++;
			if(cur>n) cur=1;
			if(live[cur]) break;
		}
	}
	printf("%d",cur);
	return 0;
}