先发发已过的代码，思想很简单，就是判断线段共线且相交的情况。不过我WA了10次，哈哈。附上AC代码。有兴趣帮忙看看我不过的代码，在后面，我搞不到为啥过不了，TL就情有可原。。。
#include <iostream> #include <cstring> #include <cmath> using namespace std; #define ZERO 1e-8 struct line { double x1; double y1; double x2; double y2; }data[10010]; int _min; int n; int _rel[10010]; //关系数组，如果数值相同表示两条线段已进行合并 //判断是否有交点 bool isIn(const line& l1, const line& l2) { if(l1.x1 >= l2.x1 && l1.x1 <= l2.x2 && l1.y1 >= l2.y1 && l1.y1 <= l2.y2) return true; if(l1.x2 >= l2.x1 && l1.x2 <= l2.x2 && l1.y2 >= l2.y1 && l1.y2 <= l2.y2) return true; if(l2.x1 >= l1.x1 && l2.x1 <= l1.x2 && l2.y1 >= l1.y1 && l2.y1 <= l1.y2) return true; if(l2.x2 >= l1.x1 && l2.x2 <= l1.x2 && l2.y2 >= l1.y1 && l2.y2 <= l1.y2) return true; return false; } //通过叉乘判断l1与l2是否共线 bool mc(const line& l1, const line& l2) { double v1x = l1.x1 - l1.x2; double v1y = l1.y1 - l1.y2; double tmpx = l2.x1 - l1.x2; double tmpy = l2.y1 - l1.y2; //叉乘不为0，即不共线 if(!(fabs(v1y * tmpx - v1x * tmpy) <= ZERO)) return false; tmpx = l2.x2 - l1.x2; tmpy = l2.y2 - l1.y2; if(!(fabs(v1y * tmpx - v1x * tmpy) <= ZERO)) return false; return true; } int main() { freopen("1.txt", "r", stdin); while(cin >> n && n != 0) { for(int i = 0; i < n; i++) { cin >> data[i].x1 >> data[i].y1 >> data[i].x2 >> data[i].y2; if(data[i].x1 > data[i].x2 || (fabs(data[i].x1 - data[i].x2) <= ZERO && data[i].y1 > data[i].y2)) { double tmp = data[i].x1; data[i].x1 = data[i].x2; data[i].x2 = tmp; tmp = data[i].y1; data[i].y1 = data[i].y2; data[i].y2 = tmp; } _rel[i] = i; } _min = n; for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { if(_rel[i] != _rel[j]) { if(mc(data[i], data[j]) && isIn(data[i], data[j])) { //更新线段 if(data[j].x1 < data[i].x1 || data[j].y1 < data[i].y1) { data[i].x1 = data[j].x1; data[i].y1 = data[j].y1; }else { data[j].x1 = data[i].x1; data[j].y1 = data[i].y1; } if(data[j].x2 > data[i].x2 || data[j].y2 > data[i].y2) { data[i].x2 = data[j].x2; data[i].y2 = data[j].y2; }else { data[j].x2 = data[i].x2; data[j].y2 = data[i].y2; } //更新为较细的_rel，以及线段 int _minindex = min(_rel[i], _rel[j]); int _maxindex = max(_rel[i], _rel[j]); for(int k = 0; k < n; k++) { if(_rel[k] == _maxindex) _rel[k] = _minindex; if(_rel[k] == _minindex) memcpy(data + k, data + i, sizeof(data[i])); } _min--; } } } } int ans = 0; //没有进行合拼的条数 for(int i = 0; i < n; i++) { if(_rel[i] == i) ans++; } cout << ans << endl; //cout << _min << endl; } return 0; }
不过的代码。。研究了很久出不来。。
#include <iostream> #include <cstring> #include <cmath> using namespace std; #define ZERO 1e-8 struct line { double x1; double y1; double x2; double y2; }data[10010]; int _min; int n; int _rel[10010]; //关系数组，如果数值相同表示两条线段已进行合并 //判断是否有交点 bool isIn(const line& l1, const line& l2) { if(fabs(l1.x1 - l2.x1) <= ZERO || fabs(l1.x1 - l2.x2) <= ZERO || fabs(l1.x2 - l2.x1) <= ZERO || fabs(l1.x2 - l2.x2) <= ZERO) return true; if(l1.x1 > l2.x1 && l1.x1 < l2.x2) return true; if(l1.x2 > l2.x1 && l1.x2 < l2.x2) return true; if(l2.x1 > l1.x1 && l2.x1 < l1.x2) return true; if(l2.x2 > l1.x1 && l2.x2 < l1.x2) return true; return false; } //通过叉乘判断l1与l2是否共线 bool mc(const line& l1, const line& l2) { double v1x = l1.x1 - l1.x2; double v1y = l1.y1 - l1.y2; double tmpx = l2.x1 - l1.x2; double tmpy = l2.y1 - l1.y2; //叉乘不为0，即不共线 if(!(fabs(v1y * tmpx - v1x * tmpy) <= ZERO)) return false; tmpx = l2.x2 - l1.x2; tmpy = l2.y2 - l1.y2; if(!(fabs(v1y * tmpx - v1x * tmpy) <= ZERO)) return false; return true; } int main() { //freopen("1.txt", "r", stdin); while(cin >> n && n != 0) { for(int i = 0; i < n; i++) { cin >> data[i].x1 >> data[i].y1 >> data[i].x2 >> data[i].y2; if(data[i].x1 > data[i].x2) { double tmp = data[i].x1; data[i].x1 = data[i].x2; data[i].x2 = tmp; tmp = data[i].y1; data[i].y1 = data[i].y2; data[i].y2 = tmp; } _rel[i] = i; } _min = n; for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { if(_rel[i] != _rel[j]) { if(mc(data[i], data[j]) && isIn(data[i], data[j])) { //找出具有最大的x和最细的x的两个坐标并更新两条线段 if(data[j].x1 < data[i].x1) { data[i].x1 = data[j].x1; data[i].y1 = data[j].y1; }else { data[j].x1 = data[i].x1; data[j].y1 = data[i].y1; } if(data[j].x2 > data[i].x2) { data[i].x2 = data[j].x2; data[i].y2 = data[j].y2; }else { data[j].x2 = data[i].x2; data[j].y2 = data[i].y2; } //更新为较细的_rel，以及线段 int _minindex = min(_rel[i], _rel[j]); int _maxindex = max(_rel[i], _rel[j]); for(int k = 0; k < n; k++) { if(_rel[k] == _maxindex) _rel[k] = _minindex; if(_rel[k] == _minindex) memcpy(data + k, data + i, sizeof(data[i])); } _min--; } } } } int ans = 0; //没有进行合拼的条数 for(int i = 0; i < n; i++) { if(_rel[i] == i) ans++; } cout << ans << endl; //cout << _min << endl; } return 0; }
