【HDOJ】1086 You can Solve a Geometry Problem too

数学题，证明AB和CD。只需证明C、D在AB直线两侧，并且A、B在CD直线两侧。
公式为：（ABxAC）*（ABxAD）<= 0 and（CDxCA）*（CDxCB）<= 0

 1 #include <stdio.h>
 2 
 3 #define MAXNUM 105
 4 
 5 typedef struct {
 6     double x1,  y1;
 7     double x2,  y2;
 8 } line_st;
 9 
10 line_st lines[MAXNUM];
11 
12 int cal(int i, int j) {
13     double ab_x, ab_y, ac_x, ac_y, ad_x, ad_y;
14     double a, b;
15 
16     ab_x = lines[i].x2 - lines[i].x1;
17     ab_y = lines[i].y2 - lines[i].y1;
18     ac_x = lines[j].x1 - lines[i].x1;
19     ac_y = lines[j].y1 - lines[i].y1;
20     ad_x = lines[j].x2 - lines[i].x1;
21     ad_y = lines[j].y2 - lines[i].y1;
22     a = ab_x*ac_y - ab_y*ac_x;
23     b = ab_x*ad_y - ab_y*ad_x;
24     if (a*b <= 0)
25         return 1;
26     else
27         return 0;
28 }
29 
30 int main() {
31     int n;
32     int i, j, k;
33 
34     while (scanf("%d", &n)!=EOF && n) {
35         for (i=0; i<n; ++i)
36             scanf("%lf%lf%lf%lf", &lines[i].x1,&lines[i].y1,&lines[i].x2,&lines[i].y2);
37         k = 0;
38         for (i=0; i<n; ++i)
39             for (j=0; j<i; ++j)
40                 if (cal(i, j) && cal(j, i))
41                     k++;
42         printf("%d
", k);
43     }
44 
45     return 0;
46 }