浙江工业大学校赛 猜猜谁是我
猜猜谁是我
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 704 Accepted Submission(s): 250
Problem Description
女神YSJ给Martin发了一个视频。“猜猜里面哪个是我。” 女神说。 作为一个脸盲，再加上多年不见，Martin已经完全不知道女神长成了什么样子，他表示完全认不出来。 好在Martin手上还有一张YSJ小时候的照片，他可以拿照片和视频里的人进行特征比对，从而找出女神。 为了简化问题，我们将YSJ小时候的脸表示成一个800行800列的矩阵，然后给出眼睛、鼻子、嘴巴的中心在脸上的坐标，全部用整数表示。视频中的其他人也都按照这个方式表示，截取正脸并且缩放到800x800以减小误差，输入不保证符合实际（例如不保证眼睛在鼻子的上方，鼻子在嘴巴上方blahblah。。） Martin进行特征比对的方式相当简单粗暴:眼睛、鼻子、嘴巴中心和YSJ小时候照片的欧氏距离总和最小的就是女神。 YSJ小时候的脸部特征描述如下, 分别表示左眼、右眼、鼻子、嘴巴的中心在图中的位置(参见输入描述)： 200 200 200 600 450 400 700 400 但是Martin的编程水平已经和他的表达能力一样烂到一定境界了，所以他希望聪明的你能够帮帮他。
Input
多组数据。每个人的人脸特征都用4行表示，每行两个整数x,y(0<=x,y<800) 分别表示左眼、右眼、鼻子、嘴巴的中心在图中的位置。。每一组数据先给出n (0< n<1000)，表示视频中出现的脸的个数，编号从1-n，接着的n*4行给出每张脸的描述。
Output
对于每组数据，输出最可能是女神的脸的编号，如果有多张人脸符合要求，输出编号最小的，单独一行。
Sample Input
3
201 201
200 600
450 400
700 400
201 200
200 600
450 400
700 400
200 201
200 600
450 400
700 400Sample Output
2#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long int ll;
struct face{
int num;
double ans;
}f[1005];
bool cmp(face a,face b){
return a.ans<b.ans;
}
int main(){
int n;
int x,y;
while(~scanf("%d",&n)){
for(int i=0;i<n;i++){
double ans=0;
scanf("%d %d",&x,&y);
ans+=sqrt(1.0*(200-x)*(200-x)+1.0*(200-y)*(200-y));
scanf("%d %d",&x,&y);
ans+=sqrt(1.0*(200-x)*(200-x)+1.0*(600-y)*(600-y));
scanf("%d %d",&x,&y);
ans+=sqrt(1.0*(450-x)*(450-x)+1.0*(400-y)*(400-y));
scanf("%d %d",&x,&y);
ans+=sqrt(1.0*(700-x)*(700-x)+1.0*(400-y)*(400-y));
f[i].ans=ans;
f[i].num=i+1;
}
sort(f,f+n,cmp);
printf("%d\n",f[0].num);
}
return 0;
}
Hint欧氏距离就是两个点的直线距离