问题 3742 --指纹比对(完善程序)

3742: 指纹比对(完善程序)★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 108  解决: 67
[提交][状态][命题人:]

题目描述

如上图所示,经典的指纹比对算法

是先将指纹图像进行预处理

提取得到特征点,每个特征点有位置信息和方向信息

针对左右两个指纹图像对应的特征点集

不妨假设左边的指纹为L,右边的指纹为R

则L中的每个特征点,只能对应R上的一个特征点,或者是不存在对应的特征点

同理,R中的每个特征点,只能对应L上的一个特征点,或者不存在对应的特征点

我们称(Li,Rj)为对应特征点对,Li为L中的一个特征点,Rj为R中的一个特征点

如果(Li,Rj)和(Lp,Rq)存在如下冲突情况:

Li==Lp 或者Rj==Rq                              

即存在一个特征点对应两个不同的特征点的情况,需要进行去重。

如果(Li,Rj)和之前选定的点对(Lp,Rq)冲突,按如下规则进行去重:

如果Lp>Li 且 Rq>Rj, 则替换

#include <iostream>
using namespace std;
int n,m;
int a[100],b[100];
int x,y,ans=0;
int main() 
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        if(a[x]<y && _____(1)______)
        {
            if(a[x]>0)  
		b[a[x]]=0;
            if(b[y]>0)  
		_____(2)______;
            a[x]=y;
            ______(3)_____;
        }
    }
    for(int i=1;_____(4)_____;i++)
    {
        if(a[i]==0) 
		++ans;
        if(______(5)_______) 
		++ans;
    }
    printf("%d\n",ans);
    return 0;
}


输入

两个正整数n<100和m<=n

其中n表示每个指纹图像的最多特征点数

m表示已经比对上的点对数目

下面m行,每行两个数xi, yi,表示L中的第xi个特征点对应R中的第yi个特征点

输出

输出L和R中没有对应特征点的特征点数量之和
样例输入
Copy
10 6
1 1
2 2
3 3
3 4
4 5
6 6
样例输出
Copy
10

提示

来源

[提交][状态]