ex1.cpp

上海交通大学本科算法大作业

#include <fstream>
#include <vector>
#include <cmath>
using namespace std;

class Line{
public:
	double ax,ay,bx,by;
	Line(double L,double H,double R,int style){
		if (style==0){
			ax=L;
			ay=by=H;
			bx=R;
		}else if (style==1){
			ax=L;
			ay=H;
			bx=L+(R-L)/2;
			by=H+(R-L)/2;
		}else if (style==2){
			ax=L+(R-L)/2;
			ay=H+(R-L)/2;
			bx=R;
			by=H;
		}
	}

	Line(double x1,double y1,double x2,double y2){
		ax=x1;
		ay=y1;
		bx=x2;
		by=y2;
	}

	static bool AtLeft(Line *l1,Line *l2){
		return l1->bx-l2->ax<1e-6;
	}

	Line* lsubline(double p){
		double nx=p;
		double ny=(by-ay)/(bx-ax)*(nx-ax)+ay;
		return new Line(ax,ay,nx,ny);
	}

	Line* rsubline(double p){
		double nx=p;
		double ny=(by-ay)/(bx-ax)*(nx-ax)+ay;
		return new Line(nx,ny,bx,by);
	}

	static bool hasIntersection(Line* l1,Line* l2){
		return (l1->by-l1->ay)*(l2->by-l2->ay)<0&&getIntersection(l1,l2)>=0;
	}

	static double getIntersection(Line* l1,Line* l2){
		double x=l1->ax+abs(l2->ay-l1->ay)/2;
		if (x<l1->bx&&x<l2->bx&&x>l1->ax&&x>l2->ax) return x;
		else return -1;
	}
};

class Profile{
public:
	vector<Line> mLines;
	Profile(){
	}
	void WriteResult(string p,int style){
		ofstream fout(p.c_str());

		double last_write_high=-1;

		for (int i=0;i<mLines.size();i++){
			if (i>0&&mLines[i].ax!=mLines[i-1].bx){
				fout<<mLines[i-1].bx<<" "<<0<<endl;
				if (style==1){
					fout<<mLines[i].ax<<" "<<0<<endl;
				}
				last_write_high=0;
			}
			if (i==0){
				fout<<mLines[i].ax<<" "<<mLines[i].ay<<endl;
				last_write_high=mLines[i].ay;
			}else{
				double lx=mLines[i-1].bx;
				double ly=mLines[i-1].by;
				if (lx==mLines[i].ax&&ly==mLines[i].ay){
					lx=mLines[i-1].ax;
					ly=mLines[i-1].ay;
				}
				double rx=mLines[i].bx;
				double ry=mLines[i].by;
				double debug=abs((ry-ly)/(rx-lx)*(mLines[i].ax-lx)+ly-mLines[i].ay);
				if (abs((ry-ly)/(rx-lx)*(mLines[i].ax-lx)+ly-mLines[i].ay)>1e-6){
					if (mLines[i].ay!=last_write_high){
						fout<<mLines[i].ax<<" "<<mLines[i].ay<<endl;
						last_write_high=mLines[i].ay;
					}
				}
			}

			if (i==mLines.size()-1){
				if (mLines[i].by!=last_write_high){
					fout<<mLines[i].bx<<" "<<mLines[i].by<<endl;
				}
				fout<<mLines[i].bx<<" "<<0<<endl;
			}else{
                double lx = mLines[i].ax;
                double ly = mLines[i].ay;
                double rx = mLines[i + 1].ax;
                double ry = mLines[i + 1].ay;
                if (rx == mLines[i].bx && ry == mLines[i].by)
                {
                    rx = mLines[i].bx;
                    ry = mLines[i].by;
                }
                if (abs((ry - ly) / (rx - lx) * (mLines[i].bx - lx) + ly - mLines[i].by)>1e-6)
                {
                    if (last_write_high != mLines[i].by)
                    {
                        fout<<mLines[i].bx<<" "<<mLines[i].by<<endl;
                    }
                    last_write_high = mLines[i].by;
                }
			}
		}
		fout.close();
	}
};

Profile *combine(Profile *lpart,Profile *rpart){
	int i=0,j=0;
	Profile *retval=new Profile();
	while (i<lpart->mLines.size()||j<rpart->mLines.size()){
		if (i==lpart->mLines.size()||j<rpart->mLines.size()&&Line::AtLeft(&(rpart->mLines[j]),&(lpart->mLines[i]))){
			retval->mLines.push_back(rpart->mLines[j++]);
		}else if (j==rpart->mLines.size()||Line::AtLeft(&(lpart->mLines[i]),&(rpart->mLines[j]))){
			retval->mLines.push_back(lpart->mLines[i++]);
		}else if (lpart->mLines[i].ax<rpart->mLines[j].ax){
			retval->mLines.push_back(*(lpart->mLines[i].lsubline(rpart->mLines[j].ax)));
			lpart->mLines[i]=*(lpart->mLines[i].rsubline(rpart->mLines[j].ax));
		}else if (rpart->mLines[j].ax<lpart->mLines[i].ax){
			retval->mLines.push_back(*(rpart->mLines[j].lsubline(lpart->mLines[i].ax)));
			rpart->mLines[j]=*(rpart->mLines[j].rsubline(lpart->mLines[i].ax));
		}else if (Line::hasIntersection(&(lpart->mLines[i]),&(rpart->mLines[j]))){
			double ix=Line::getIntersection(&(lpart->mLines[i]),&(rpart->mLines[j]));
			if (lpart->mLines[i].ay>rpart->mLines[j].ay){
				retval->mLines.push_back(*(lpart->mLines[i].lsubline(ix)));
			}else{
				retval->mLines.push_back(*(rpart->mLines[j].lsubline(ix)));
			}
			lpart->mLines[i]=*(lpart->mLines[i].rsubline(ix));
			rpart->mLines[j]=*(rpart->mLines[j].rsubline(ix));
		}else{
			double ex=(lpart->mLines[i].bx>rpart->mLines[j].bx)?rpart->mLines[j].bx:lpart->mLines[i].bx;
			if (lpart->mLines[i].ay>rpart->mLines[j].ay){
				retval->mLines.push_back(*(lpart->mLines[i].lsubline(ex)));
			}else{
				retval->mLines.push_back(*(rpart->mLines[j].lsubline(ex)));
			}
			lpart->mLines[i]=*(lpart->mLines[i].rsubline(ex));
			rpart->mLines[j]=*(rpart->mLines[j].rsubline(ex));
			if (lpart->mLines[i].ax==lpart->mLines[i].bx) i++;
			if (rpart->mLines[j].ax==rpart->mLines[j].bx) j++;
		}
	}
	return retval;
}


Profile *calc(vector<Profile*> profile,int l,int r){
	if (l==r) return profile[l];
	Profile* lpart=calc(profile,l,(l+r)/2);
	Profile* rpart=calc(profile,(l+r)/2+1,r);
	return combine(lpart,rpart);
}

int main(){
	ifstream fin("data3.txt");
	int n;
	fin>>n;
	vector<Profile*> flat,tri;
	
	for (int i=0;i<n;i++){
		double L,H,R;
		fin>>L>>H>>R;
		Profile* tf=new Profile();
		Profile* tt1=new Profile();
		Profile* tt2=new Profile();
		Line l1(L,H,R,0);
		tf->mLines.push_back(l1);
		Line l2(L,H,R,1);
		tt1->mLines.push_back(l2);
		Line l3(L,H,R,2);
		tt2->mLines.push_back(l3);
		tri.push_back(tt1);
		tri.push_back(tt2);
		flat.push_back(tf);
	}

	Profile* flat_res=calc(flat,0,n-1);
	flat_res->WriteResult("result.out",0);
	Profile* tri_res=calc(tri,0,n+n-1);
	tri_res->WriteResult("result.out2",1);
	return 0;
}