猜猜谁是我

怼烎@ 2022-09-30 06:08 168阅读 0赞

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 400

Sample Output

2
    
    
       
        
        
         
         
          Hint
        
         
        
         欧氏距离就是两个点的直线距离

\#include<stdio.h>  
\#include<math.h>  
int main()  
\{  
int i,j,n;  
int u,v;  
int m;  
double x,y,z;  
double min;  
int cmp\[4\]\[2\]=\{ \{200,200\},\{200,600\},\{450,400\},\{700,400\}\};  
double sum\[1000\]=\{0\};  
while(scanf("%d",&n)!=EOF)  
\{  
memset(sum,0,sizeof(sum));  
for(i=0;i<n;i++)  
\{  
for(j=0;j<4;j++)  
\{  
scanf("%d%d",&u,&v);  
x=u-cmp\[j\]\[0\];  
y=v-cmp\[j\]\[1\];  
z=sqrt(x\*x+y\*y);  
sum\[i\]+=z;  
\}  
\}  
min=0x3f3f3f3f;  
u=0;  
for(i=0;i<n;i++)  
\{  
if(sum\[i\]<min)  
\{  
min=sum\[i\];  
u=i;  
\}  
\}  
m=u+1;  
printf("%d\\n",m);  
\}  
return 0;  
\}