本文主要是介绍HDU 3659 Identify the number(数字识别 模拟)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3659
这个题目刚开以为是计算几何，其实是个毛线啊，就是一模拟题，不过这个题想AC还是需要花点时间想的，其实也比较简单，关键是细心
题意：给定你n条线段，每条线段长度为1，这么多线段会组合成数字（见题目图），每个数字之间的间隔5以上，让你从左到右输出数字
解题思路：
首先肯定是按照线段较小的x排序了，排序完成之后开始分组，每一组肯定是一个数字，然后判断这个数字是什么
首先当这个组的线段个数为2 3 4 7的时候可以直接得出表示的数字是什么，因为这几个数量唯一确定一个数字
然后就是6，可能的结果是0和6，这个好办，只要判断存在某点与另外所有点都不相交就确定是6，否则0
最后是5，这个题目核心就在5这里，2 3 5，到底是哪个，3的话好判断，只要存在一个点与另外两点有相交一定是3
最恶心的是2 和 5的判断，奶奶的镜面对称，想一会其实还是可以判断的
首先找出只有一个顶点和另外顶点相交的两条线段，同时记录是a端有相交还是b端有相交（a端指的是线段x值较小的一端，x相同y较小的）
然后找出两条线段相对位置低的那条，这时候要求的是低的那条一定是a端相交才是2，否则是5，如果是睡着的2，那么判断右边那条一定要是
a端相交！
（开始搞错直接判断右边的导致wa数次）
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
using namespace std;
#define maxn 15000
struct point{double x,y;bool operator == (const point &a) const{return a.x==x && a.y==y;}
}temp;
struct line{point a,b;
}po[maxn];
int n;
bool cmp(const line &a,const line &b){return a.a.x < b.a.x;
}
int function6(int l,int r){int i,k,j;for(i=l;i<=r;i++){for(j=l;j<=r;j++){if(i==j) continue;if(po[i].a==po[j].a || po[i].a==po[j].b) break;}if(j==r+1){ printf("6");return 0;}for(j=l;j<=r;j++){if(i==j) continue;if(po[i].b==po[j].a || po[i].b==po[j].b) break;}if(j==r+1){ printf("6");return 0;}}printf("0");return 0;
}
int function5(int l,int r){int i,j,k,count,t;line rec[10],tem;bool flag[10];memset(flag,false,sizeof(flag));t=0;for(i=l;i<=r;i++){count=0;for(j=l;j<=r;j++){if(i==j)continue;if(po[i].a==po[j].a || po[i].a==po[j].b)count++;}if(count==0){ rec[t]=po[i];flag[t++]=false;}//flag的意思是表示a这端相交没，false表示没相交if(count>=2){ printf("3"); return 0;}count=0;for(j=l;j<=r;j++){if(i==j)continue;if(po[i].b==po[j].a || po[i].b==po[j].b)count++;}if(count>=2){ printf("3"); return 0;}if(count==0){ rec[t]=po[i];flag[t++]=true;}}if(MIN(rec[0].a.y,rec[0].b.y) < MIN(rec[1].a.y,rec[1].b.y)){if(flag[0]){printf("2");return 0;}else {printf("5");return 0;}}else if(MIN(rec[0].a.y,rec[0].b.y) == MIN(rec[1].a.y,rec[1].b.y)){if(rec[0].a.x > rec[1].b.x){if(flag[0]){printf("2");return 0;}else {printf("5");return 0;}}else {if(flag[1]){printf("2");return 0;}else {printf("5");return 0;}}}else{if(flag[1]){printf("2");return 0;}else {printf("5");return 0;}}return 0;
}
int main(){int i,j,k,l,r;double Max;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++){scanf("%lf%lf%lf%lf",&po[i].a.x,&po[i].a.y,&po[i].b.x,&po[i].b.y);if(po[i].a.x > po[i].b.x)temp=po[i].a,po[i].a=po[i].b,po[i].b=temp;else if(po[i].a.x == po[i].b.x && po[i].a.y > po[i].b.y)temp=po[i].a,po[i].a=po[i].b,po[i].b=temp;}sort(po,po+n,cmp);l=0,r=0;Max=po[0].b.x;for(i=1;i<n;i++){if(po[i].a.x-Max > 5.0 || i==n-1){if(i!=n-1)r=i-1;elser=i;switch(r-l+1){case 2:printf("1");break;case 4:printf("4");break;case 3:printf("7");break;case 7:printf("8");break;case 6:function6(l,r);break;case 5:function5(l,r);break;default:while(1);}l=i;Max=po[i].b.x;}Max=MAX(Max,po[i].b.x);}printf("\n");}return 0;
}
这篇关于HDU 3659 Identify the number(数字识别 模拟)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
