#include <iostream> #include <vector> //上面这些全是铺垫……算法请从75行开始看,主函数在110行 using namespace std; class Line{ public: int left;//左端点 int right;//右端点 private: vector<Line*> intersectLines;//与本线断重叠的线段 public: Line(int x1 , int x2): left(x1 < x2 ? x1 : x2), right(x1 < x2 ? x2 : x1){} //两条线段是否有内部公共点 bool intersect(Line *l){ if(left < l->left && right > l->left){ return true; } if(right > l->right && left < l->right){ return true; } if(left >= l->left && right <= l->right){ return true; } return false; } //添加相交线段 void addIntersectLine(Line* l){ intersectLines.push_back(l); } intersectLines.push_back(l); } //移除相交线段 void removeIntersectLine(Line* l){ for(vector<Line*>::iterator it = intersectLines.begin() ; it != intersectLines.end() ; ++it ){ if(*it == l){ intersectLines.erase(it); return; } } } //移除所有相交线段 void clearIntersectLines(){ intersectLines.clear(); } //相交线段个数 int intersectSize(){ return intersectLines.size(); } }; //将Line按重叠数从大到小排序,懒得快排了…… void sortLines(Line** lines,int size){ for(int i = 0 ; i < size ; ++i){ for(int j = i + 1 ; j < size ; ++j){ if(lines[i]->intersectSize() < lines[j]->intersectSize()){ Line* temp = lines[i]; lines[i] = lines[j]; lines[j] = temp; } } } } //看清楚!!上面全是铺垫,这才是算法!! int getRemainNum(Line** lines,int size){ if(size <= 1){ int getRemainNum(Line** lines,int size){ if(size <= 1){ return size; } //首先计算每条线段与几条线段相交 for(int i = 0 ; i < size ; ++i){ for(int j = i + 1 ; j < size ; ++j){ if(lines[i]->intersect(lines[j])){ lines[i]->addIntersectLine(lines[j]); lines[j]->addIntersectLine(lines[i]); } } } sortLines(lines,size); int res = size; //如果还有线段相交,就删去(与别的线段交点最多的线段) while(lines[0]->intersectSize() > 0){ //printLines(lines,size); lines[0]->clearIntersectLines(); for(int i = 1 ; i < size ; ++i){ lines[i]->removeIntersectLine(lines[0]); } --res; sortLines(lines,size); } return res; } int main() { //输入数据 { //输入数据 int num , x1 , x2; scanf("%d",&num); if(num <= 0 || num > 100){ return 0; } Line* lines[num]; for(int i = 0 ; i < num ; ++i){ scanf("%d %d",&x1,&x2); lines[i] = new Line(x1,x2); } int res = getRemainNum(lines , num); cout << res << endl; return 0; }