2014
11-30

# 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.

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

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;
}


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;