[UVA][幾何] 11343 - Isolated Segments
D - Isolated Segments
Time Limit: 1 sec
Memory Limit: 16MB
You're given n segments in the rectangular coordinate system. The segments are defined by start and end points (Xi,Yi) and (Xj,Yj) (1 <= i, j <= n). Coordinates of these points are integer numbers with real value smaller then 1000. Length of each segment is positive.
When 2 segments don't have a common point then it is said that segments don't collide. In any other case segments collide. Be aware that segments collide even if they have only one point in common.
Segment is said to be isolated if it doesn't collide with all the other segments that are given, i.e. segment i is isolated when for each 1 <= j <= n, (i != j), segments i and j don`t collide. You are asked to find number T - how many segments are isolated.
INPUT:
First line of input contains number N (N <= 50), then tests follow. First line of each test case contains number M (M <= 100) - the number of segments for this test case to be considered. For this particular test case M lines follow each containing a description of one segment. Segment is described by 2 points: start point (Xpi,Ypi) and end point (Xei,Yei). They are given in such order: Xpi Ypi Xei YeiOUTPUT:
For each test case output one line containing number T.SAMPLE INPUT:
6
3
0 0 2 0
1 -1 1 1
2 2 3 3
2
0 0 1 1
1 0 0 1
2
0 0 0 1
0 2 0 3
2
0 0 1 0
1 0 2 0
2
0 0 2 2
1 0 1 1
2
1 3 1 5
1 0 1 6
SAMPLE OUTPUT:
1
0
2
0
0
0
我想用 int 過不了, 大概是計算外積時溢位了
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
struct Point {
double x, y;
};
struct Segment {
Point s, t;
};
double in(double a, double b, double c) {
return c >= a && c <= b;
}
int onLine(Segment a, Point c) {
static double minx, maxx, miny, maxy;
minx = min(a.s.x, a.t.x);
maxx = max(a.s.x, a.t.x);
miny = min(a.s.y, a.t.y);
maxy = max(a.s.y, a.t.y);
if(in(minx, maxx, c.x) != 0 && in(miny, maxy, c.y) != 0) {
if((a.s.x-a.t.x)*(c.y-a.s.y) == (a.s.y-a.t.y)*(c.x-a.s.x)) {
return 1;
}
}
return 0;
}
double cross(Point &o, Point &a, Point &b) {
return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int intersection(Segment a, Segment b) {
if(onLine(a, b.s) || onLine(a, b.t) || onLine(b, a.s) || onLine(b, a.t))
return 1;
if(cross(a.s, a.t, b.s)*cross(a.s, a.t, b.t) < 0 &&
cross(a.t, a.s, b.s)*cross(a.t, a.s, b.t) < 0 &&
cross(b.s, b.t, a.s)*cross(b.s, b.t, a.t) < 0 &&
cross(b.t, b.s, a.s)*cross(b.t, b.s, a.t) < 0
)
return 1;
return 0;
}
int main() {
int t, n, i, j;
Segment line[1000];
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%lf %lf %lf %lf", &line[i].s.x, &line[i].s.y, &line[i].t.x, &line[i].t.y);
int ans = 0;
for(i = 0; i < n; i++) {
int flag = 0;
for(j = 0; j < n; j++) {
if(i == j)
continue;
if(intersection(line[i], line[j])) {
flag = 1;
break;
}
}
if(flag == 0)
ans++;
}
printf("%d\n", ans);
}
return 0;
}