Baudelaire is Programmer

Closed Fences

计算几何，借鉴了很多，写的很辛苦，因为需要考虑不少特殊情况。用二分法分割篱笆来探索每个篱笆能不能被看到，注意要设置一个分段长度的下限。在判断线段是否相交时有一些技巧。借鉴了一下混合积的方法，发现不能处理两个线段共线的情况。我判断共线和共线情况下线段是否相交的方法如下：设坐标系oxyz中两个线段ab和cd处于oxy平面上，若ab×ac与ab×ad的z分量都为0则abcd共线。共线的情况下，若ac*ad>0且bc*bd>0，则两线段不相交，否则相交。

/*
ID: huilong1
LANG: C++
TASK: fence4
*/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define ESP 1e-4
FILE *fin,*fout;

typedef struct{
	double x;
	double y;
}Point;

typedef struct{
	Point a;
	Point b;
}Seg;

typedef struct{
	double x;
	double y;
	double z;
}Vector;

int N;
Seg fence[201];
Point obser;
Point corner[201];
Seg visible[201];
int numsee;

//判断是否是相邻的篱笆 
bool neighbor(int i,int j){
	if(i==0&&j==N-1||i==N-1&&j==0)return true;
	int abs=i-j;
	if(abs<0)abs=-abs;
	if(abs==1)return true;
	return false;
}

//获得中点
Point getmiddle(Point a,Point b){
	Point m;
	m.x=(a.x+b.x)/2;
	m.y=(a.y+b.y)/2;
	return m;
}

//算点积
double dotpro(Vector a,Vector b){
	return a.x*b.x+a.y*b.y+a.z*b.z;
}

//算叉积
Vector crosspro(Vector a,Vector b){
	Vector t;
	t.x=a.y*b.z-a.z*b.y;
	t.y=a.z*b.x-a.x*b.z;
	t.z=a.x*b.y-a.y*b.x;
	return t;
} 

//获得两点决定的向量
Vector getvector(Point a,Point b){
	Vector t;
	t.x=b.x-a.x;
	t.y=b.y-a.y;
	t.z=0;
	return t;
} 

//判断线段是否交叉
bool cross(Seg p,Seg q){
	Vector pv=getvector(p.a,p.b);
	Vector qv=getvector(q.a,q.b);
	Vector paqa=getvector(p.a,q.a);
	Vector paqb=getvector(p.a,q.b);
	Vector pbqa=getvector(p.b,q.a);
	Vector pbqb=getvector(p.b,q.b);
	Vector qapa=getvector(q.a,p.a);
	Vector qapb=getvector(q.a,p.b);
	//判断两线段是否共线
	Vector v1=crosspro(pv,paqa);
	Vector v2=crosspro(pv,paqb);
	if(v1.z==v2.z&&v1.z==0){//共线 
		if(dotpro(paqa,paqb)>0&&dotpro(pbqa,pbqb)>0)return false;
		else return true;
	}
	//不共线 
	if(dotpro(v1,v2)>0)return false;
	if(dotpro(crosspro(qv,qapa),crosspro(qv,qapb))>0)return false;
	return true;
} 

//判断是否能看到点
int seepoint(Point p,int ind){
	Seg view;
	view.a=obser;
	view.b=p;
	for(int i=0;i<N;i++){
		if(i==ind)continue;
		if(cross(view,fence[i]))return i;
	}
	return -1;
} 

//判断线段是否收缩为一个点 
bool ispoint(Seg s){
	Point a=s.a;
	Point b=s.b;
	if((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)<ESP)return true;
	return false;
}

//判断是否可见 
bool cansee(Seg s,int ind){
	if(ispoint(s))return false;
	Point a=s.a;
	Point b=s.b;
	Point mid=getmiddle(a,b);
	int sta,stb,stmid;
	sta=seepoint(a,ind);
	stb=seepoint(b,ind);
	stmid=seepoint(mid,ind);
	if(sta==stb&&sta>=0)return false;
	if(sta<0||stb<0||stmid<0)return true;
	Seg t;
	t.a=a,t.b=mid;
	if(cansee(t,ind))return true;
	t.a=mid,t.b=b;
	if(cansee(t,ind))return true;
	return false;
} 

int main(){
	fin=fopen("fence4.in","r");
	fout=fopen("fence4.out","w");
	fscanf(fin,"%d",&N);
	fscanf(fin,"%lf %lf",&obser.x,&obser.y);
	for(int i=0;i<N;i++){
		fscanf(fin,"%lf %lf",&corner[i].x,&corner[i].y);
	}
	
	//按顺序生成篱笆 
	for(int i=0;i<=N-2;i++){
		fence[i].a=corner[i];
		fence[i].b=corner[i+1];
	}
	fence[N-1].a=corner[0];
	fence[N-1].b=corner[N-1];
	
	//判断篱笆合法性 （不相邻的不能相交） 
	for(int i=0;i<N;i++){
		for(int j=0;j<i-1;j++){
			if(!neighbor(i,j)&&cross(fence[i],fence[j])){
				//printf("%d %d\n",i,j);
				//system("pause");
				fprintf(fout,"NOFENCE\n");
				return 0;
			}
		}
	}
	
	//为了按顺序输出 调整篱笆顺序 
	Seg t=fence[N-1];
	fence[N-1]=fence[N-2];
	fence[N-2]=t;
	
	for(int i=0;i<N;i++){
		if(cansee(fence[i],i)){
			visible[numsee]=fence[i];
			numsee++;
		}
	}
	fprintf(fout,"%d\n",numsee);
	for(int i=0;i<numsee;i++){
		fprintf(fout,"%.0lf %.0lf %.0lf %.0lf\n",visible[i].a.x,visible[i].a.y,visible[i].b.x,visible[i].b.y);
	}
	//system("pause");
	return 0;
}

 

American Heritage

给一个二叉树的前序遍历和中序遍历，求后序遍历。设计一个递归式，不用重构整个二叉树。

/*
ID: huilong1
LANG: C++
TASK: heritage
*/
#include<stdio.h>
#include<stdlib.h>

FILE *fin,*fout;
char in[26];
int hashin[26];
char pre[26];
int num;

void showpost(int prebeg,int preend,int inbeg,int inend){
	if(prebeg>preend)return;
	showpost(prebeg+1,
	         prebeg+hashin[pre[prebeg]-'A']-inbeg,
			 inbeg,
			 hashin[pre[prebeg]-'A']-1);
	showpost(prebeg+hashin[pre[prebeg]-'A']-inbeg+1,
             prebeg+hashin[pre[prebeg]-'A']-inbeg+inend-hashin[pre[prebeg]-'A'],
			 hashin[pre[prebeg]-'A']+1,
			 inend);
	fprintf(fout,"%c",pre[prebeg]);
	return;
}

int main(){
	fin=fopen("heritage.in","r");
	fout=fopen("heritage.out","w");
	while(fscanf(fin,"%c",&in[num])&&in[num]!='\n'){
		hashin[in[num]-'A']=num;
		num++;
	}
	int i;
	for(i=0;i<num;i++)fscanf(fin,"%c",&pre[i]);
	showpost(0,num-1,0,num-1);
	fprintf(fout,"\n");
	//system("pause");
	return 0;
}

 

Electric Fence

用解析法解决了，后来发现可以简单地使用皮克公式。

 

Raucous Rockers

背包问题的变形，我加了一维用来表示唱片的数量。用dp[m][t][n]表示前m张唱片，最后一张唱片剩下t分钟，从前n首歌中选歌时可以选的最大歌曲数。则有：

dp[m][t][n]=max{ dp[m][t][n-1],

                 dp[m][t-time(n)][n-1]+1 ( if time(n)<=t ),

                 dp[m-1][T-time(n)][n-1]+1 ( if time(n)>t )

            }

---

皮克公式（Pick's theorem）

给定顶点座标均是整点（或正方形格点）的简单多边形，皮克定理说明了其面积A和内部格点数目i、边上格点数目b的关系：A = i + b/2 - 1。

 

设观察点为O，取线段AB，及AB中点C，连结AO、BO、CO；

1. 枚举所有线段，若AO、BO与同一条线段相交，则AB看不到。

2. 若A、B很近，则AB可以看成质点，AB看不到。

3. 枚举所有线段，分别与AO、BO、CO求是否相交，循环结束后判断是否有一条线段（AO、BO、CO）没有相交，如果有，则AB可以看见。

4. 二分AB， 对AC、BC进行上述过程。