链接：http://acm.hdu.edu.cn/showproblem.php?pid=1558
Segment set
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5635 Accepted Submission(s): 2179
Problem Description
A segment and all segments which are connected with it compose a segment set. The size of a segment set is the number of segments in it. The problem is to find the size of some segment set.
Input
In the first line there is an integer t - the number of test case. For each test case in first line there is an integer n (n<=1000) - the number of commands.
There are two different commands described in different format shown below:
P x1 y1 x2 y2 - paint a segment whose coordinates of the two endpoints are (x1,y1),(x2,y2).
Q k - query the size of the segment set which contains the k-th segment.
k is between 1 and the number of segments in the moment. There is no segment in the plane at first, so the first command is always a P-command.
Output
For each Q-command, output the answer. There is a blank line between test cases.
Sample Input
1 10 P 1.00 1.00 4.00 2.00 P 1.00 -2.00 8.00 4.00 Q 1 P 2.00 3.00 3.00 1.00 Q 1 Q 3 P 1.00 4.00 8.00 2.00 Q 2 P 3.00 3.00 6.00 -2.00 Q 5
Sample Output
1 2 2 2 5
Author
LL
Source
HDU 2006-12 Programming Contest
会告诉你n个指令，然后对于P指令就是在添加一条线段，而Q就是查询编号为x的线段与它相交的线段有多少个（线段编号默认为线段添加顺序）
很简单，对于相交的线段进行并查集合并就可以，判断相交的时候可以用跨立实验来判断(也可以用叉积来判断)
注意输出格式（PE了我好几次）
代码：
#include <bits/stdc++.h>
#include <time.h>
#define first fi
#define second seusing namespace std;typedef long long ll;
typedef double db;
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
const double eps = 1e-9;
typedef pair<int,int> P;
const int maxn = 5000;
const ll mod = 1e9 + 7;
inline int sign(db a) {return a < -eps ? -1 : a > eps;
}
ll mul(ll a,ll b,ll c) {ll res = 1;while(b) {if(b & 1) res *= a,res %= c;a *= a,a %= c,b >>= 1;}return res;
}
ll phi(ll x) {ll res = x;for(ll i = 2; i * i <= x; i++) {if(x % i == 0) res = x / i * (i - 1);while(x % i == 0) x /= i;}if(x > 1) res = res / x * (x - 1);return res;
}
ll c,n,k,m;
int fa[maxn];
int Find(int x) {if(x != fa[x]) fa[x] = Find(fa[x]);return fa[x];
}
struct POINT {double x;double y;POINT(double a = 0, double b = 0) {x = a; //constructory = b;}
};
struct LINESEG { //Line SegmentPOINT s;POINT e;LINESEG(POINT a, POINT b) {s = a;e = b;}LINESEG() { }
} g[maxn];
double multiply(POINT sp, POINT ep, POINT op) {return( (sp.x - op.x) * (ep.y - op.y) - (ep.x - op.x) * (sp.y - op.y) );
}
bool intersect(LINESEG u, LINESEG v) {return( ( max(u.s.x, u.e.x) >= min(v.s.x, v.e.x) ) && //排斥实验( max(v.s.x, v.e.x) >= min(u.s.x, u.e.x) ) &&( max(u.s.y, u.e.y) >= min(v.s.y, v.e.y) ) &&( max(v.s.y, v.e.y) >= min(u.s.y, u.e.y) ) &&( multiply(v.s, u.e, u.s) * multiply(u.e, v.e, u.s) >= 0 ) && //跨立实验( multiply(u.s, v.e, v.s) * multiply(v.e, u.e, v.s) >=0 ) );
}
bool vis[maxn];
int main() { int t; scanf("%d",&t);while(t--) {int cnt = 0;memset(vis,0,sizeof(vis)); scanf("%d",&n);for(int i = 0; i <= n; i++) fa[i] = i;for(int i = 1; i <= n; i++) {POINT a,b;char op[2];scanf("%s",op); if(op[0] == 'P') {scanf("%lf",&a.x);scanf("%lf",&a.y);scanf("%lf",&b.x);scanf("%lf",&b.y); g[cnt++] = LINESEG(a,b);for(int j = cnt - 2; j >= 0; j--) {if(intersect(g[cnt - 1],g[j])) {int X = Find(cnt - 1);int Y = Find(j); if(X != Y)fa[Y] = X;}}} else {int x;scanf("%d",&x);x--;for(int i = 0; i < cnt; i++) fa[i] = Find(i); int ans = 0;for(int i = 0; i < cnt; i++) { if(fa[i] == fa[x]) ans++; }printf("%d\n",ans); }}if(t != 0)cout << endl;}//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}