HDU1086_You can Solve a Geometry Problem too(幾何/フォーク判定点線関係)

2092 ワード

問題解決レポート
テーマゲート
タイトル:
線分がどれだけ交差するかを求めます.
考え方:
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