HDU1086_You can Solve a Geometry Problem too(幾何/フォーク判定点線関係)
問題解決レポート
テーマゲート
タイトル:
線分がどれだけ交差するかを求めます.
考え方:
AB,CDの2つの線分が交差し,
すなわち、C,Dの2点は線分ABの両端にある.A,Bの2点は線分CDの両端にある.
フォーク積で点が線分の左右にあると判断します.
You can Solve a Geometry Problem too
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7347 Accepted Submission(s): 3573
Problem Description
Many geometry(幾何学)problems were designed in the ACM/ICCC.And now,I also prepare a geometry problem for this final exam.According to the experience of many ACMers,geometry problems are always much trouble,but this problem is very easy,after all we are now attending an exam,not a contest:)
Give you N(1<=N<=100)segments(線分)、please output the number of all intersections(交点).You should count repeatedly if M(M>2)segments intersect at the same point.
Note:
You can assume that two segments would not intersect at more than one point.
Input
Input contains multiple test cases. Each test case contains a integer N (1=N<=100) in a line first, and then N lines follow. Each line describes one segment with four float values x1, y1, x2, y2 which are coordinates of the segment’s ending.
A test case starting with 0 terminates the input and this test case is not to be processed.
Output
For each case, print the number of intersections, and one line one case.
Sample Input
2 0.00 0.00 1.00 1.00 0.00 1.00 1.00 0.00 3 0.00 0.00 1.00 1.00 0.00 1.00 1.00 0.000 0.00 0.00 1.00 0.00 0
Sample Output
1 3
Author
lcy
テーマゲート
タイトル:
線分がどれだけ交差するかを求めます.
考え方:
AB,CDの2つの線分が交差し,
すなわち、C,Dの2点は線分ABの両端にある.A,Bの2点は線分CDの両端にある.
フォーク積で点が線分の左右にあると判断します.
#include
#include
#include
using namespace std;
struct Point {
double x,y;
};
struct Seg {
Point l,r;
} L[110];
double xmulti(Point a,Point b,Point p) {
return (b.x-a.x)*(p.y-a.y)-(p.x-a.x)*(b.y-a.y);
}
int main() {
int n,cnt,i,j;
while(cin>>n&&n) {
cnt=0;
memset(L,0,sizeof(L));
for(i=0; i
You can Solve a Geometry Problem too
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7347 Accepted Submission(s): 3573
Problem Description
Many geometry(幾何学)problems were designed in the ACM/ICCC.And now,I also prepare a geometry problem for this final exam.According to the experience of many ACMers,geometry problems are always much trouble,but this problem is very easy,after all we are now attending an exam,not a contest:)
Give you N(1<=N<=100)segments(線分)、please output the number of all intersections(交点).You should count repeatedly if M(M>2)segments intersect at the same point.
Note:
You can assume that two segments would not intersect at more than one point.
Input
Input contains multiple test cases. Each test case contains a integer N (1=N<=100) in a line first, and then N lines follow. Each line describes one segment with four float values x1, y1, x2, y2 which are coordinates of the segment’s ending.
A test case starting with 0 terminates the input and this test case is not to be processed.
Output
For each case, print the number of intersections, and one line one case.
Sample Input
2 0.00 0.00 1.00 1.00 0.00 1.00 1.00 0.00 3 0.00 0.00 1.00 1.00 0.00 1.00 1.00 0.000 0.00 0.00 1.00 0.00 0
Sample Output
1 3
Author
lcy