首页 > ACM题库 > HDU-杭电 > HDU 3659-Identify the number-模拟-[解题报告]HOJ
2014
11-30

HDU 3659-Identify the number-模拟-[解题报告]HOJ

Identify the number

问题描述 :

Taly likes to take photographs. Because he is interested in geometry and graphics. One day, he went to a museum which exhibits all kinds of things of Mars people. He is surprised that the Mars people use the arabic numberals as human beings. But they only use the number from 0 to 8 and they like to write the numbers in a skew style as the gure sees. Then Taly took many photographs of the number writing (in fact,it is forbidden to take photograph in the so mystical museum). When home, he transformed these photograph into the graph on a 2 - D plane. Taly is confused that how to identify the numbers automatically. Now Taly ask help to you to write a program to identify the numbers.

How many words

输入:

For each test case, the first line is the number n which indicates the number of the segments. Then n lines follow, each line has four float numbers which are x1, y1, x2, y2 with precision up to 6 decimal places. (x1, y1), (x2, y2) are the two endpoints of the segment. Each segment has the same length 1 and one segment connects at least another one. For any line which is paralleled with y-axis and has width of 5, it won’t cross more than one number. It means that the minimum absolute di erence of two number’s x coordinate is at least 5.
2 ≤ n ≤ 1000, -10000 ≤ x1, y1, x2, y2 ≤ 10000.

输出:

For each test case, the first line is the number n which indicates the number of the segments. Then n lines follow, each line has four float numbers which are x1, y1, x2, y2 with precision up to 6 decimal places. (x1, y1), (x2, y2) are the two endpoints of the segment. Each segment has the same length 1 and one segment connects at least another one. For any line which is paralleled with y-axis and has width of 5, it won’t cross more than one number. It means that the minimum absolute di erence of two number’s x coordinate is at least 5.
2 ≤ n ≤ 1000, -10000 ≤ x1, y1, x2, y2 ≤ 10000.

样例输入:

12
-6.000000 2.000000 -6.000000 3.000000
-6.000000 3.000000 -6.000000 4.000000
0.707107 -0.707107 0.000000 0.000000
0.000000 0.000000 0.707107 0.707107
0.707107 0.707107 1.414213 0.000000
1.414213 0.000000 2.121320 0.707107
2.121320 0.707107 1.414213 1.414213
9.707107 -0.707107 9.000000 0.000000
9.000000 0.000000 9.707107 0.707107
9.707107 0.707107 10.414213 0.000000
9.707107 0.707107 10.414213 1.414213
11.121320 0.707107 10.414213 1.414213

样例输出:

123

题目链接: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;
                else
                r=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;
}

参考:http://blog.csdn.net/sunrain_chy/article/details/11129473


  1. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  2. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。

  3. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?