1165.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<algorithm>
#include<vector>
#include<iostream>
#include<fstream>
using namespace std;
class point{
public:
	int x,int y;
	point(int a,int b){x=a;y=b;}
};
class line{
public:
	long double k,p;
	vector<point> vecp;
	vector<int> vecu;
    line(long double kk,long double pp,int s){k=kk;p=pp;vecu.resize(s);}
};
int cmp1(const point & a,const point & b){
    if(a.x!=b.x) return a.x<b.x;
	else return a.y<b.y;
}
int cmp2(const line & a,const line & b){
    if(!(a.vecp[0].x==b.vecp[0].x&&a.vecp[0].y==b.vecp[0].y)) return cmp1(a.vecp[0],b.vecp[0]);
	else return cmp1(a.vecp[1],b.vecp[1]);
}
int main(){
    //ifstream cin("in.txt");
	int x,y,i,j,l,f;
	long double k,p;
    while(cin>>x>>y&&!(x==0&&y==0)){
       vector<point> vec;
	   vector<line> vecl;
	   vec.push_back(point(x,y));
	   while(cin>>x>>y&&!(x==0&&y==0)) vec.push_back(point(x,y));
       for(i=0;i<vec.size()-1;i++)
		   for(j=i+1;j<vec.size();j++){
               if(vec[i].x==vec[j].x) {k=10000000000000000;p=vec[i].x;}
			   else if(vec[i].y==vec[j].y) {k=0;p=vec[i].y;}
			   else{
                   k=(vec[j].y-vec[i].y)/(vec[j].x-vec[i].x);
				   p=vec[i].y-(vec[i].x*k);
			   }
			   for(l=0;l<vecl.size();l++){
				   if(k==vecl[l].k&&vecl[l].p==p) {
					   if(vecl[l].vecu[i]==0) {vecl[l].vecu[i]=1;vecl[l].vecp.push_back(vec[i]);}
					   if(vecl[l].vecu[j]==0) {vecl[l].vecu[j]=1;vecl[l].vecp.push_back(vec[j]);}
					   break;
				   }
			   }
			   if(l==vecl.size()){
                   vecl.push_back(line(k,p,vec.size()));
				   vecl[l].vecu[j]=1;vecl[l].vecp.push_back(vec[j]);
				   vecl[l].vecu[i]=1;vecl[l].vecp.push_back(vec[i]);
			   }
		   }
		for(i=0;i<vecl.size();i++){
			if(vecl[i].vecp.size()==2){vecl.erase(&vecl[i]);i-=1;}
			else sort(vecl[i].vecp.begin(),vecl[i].vecp.end(),cmp1);
		}
		sort(vecl.begin(),vecl.end(),cmp2);
		if(vecl.size()==0) cout<<"No lines were found\n";
		else {
            cout<<"The following lines were found:\n";
			for(i=0;i<vecl.size();i++){
				for(j=0;j<vecl[i].vecp.size();j++){
                   cout<<"("<<vecl[i].vecp[j].x<<","<<vecl[i].vecp[j].y<<")";
				}
				cout<<endl;
			}
		}
	}//while
}