【HDOJ】1086 You can Solve a Geometry Problem too

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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

 #include <stdio.h>

 #define MAXNUM 105

 typedef struct {

     double x1,  y1;

     double x2,  y2;

 } line_st;

 line_st lines[MAXNUM];

 int cal(int i, int j) {

     double ab_x, ab_y, ac_x, ac_y, ad_x, ad_y;

     double a, b;

     ab_x = lines[i].x2 - lines[i].x1;

     ab_y = lines[i].y2 - lines[i].y1;

     ac_x = lines[j].x1 - lines[i].x1;

     ac_y = lines[j].y1 - lines[i].y1;

     ad_x = lines[j].x2 - lines[i].x1;

     ad_y = lines[j].y2 - lines[i].y1;

     a = ab_x*ac_y - ab_y*ac_x;

     b = ab_x*ad_y - ab_y*ad_x;

     if (a*b <= )

         return ;

     else

         return ;

 }

 int main() {

     int n;

     int i, j, k;

     while (scanf("%d", &n)!=EOF && n) {

         for (i=; i<n; ++i)

             scanf("%lf%lf%lf%lf", &lines[i].x1,&lines[i].y1,&lines[i].x2,&lines[i].y2);

         k = ;

         for (i=; i<n; ++i)

             for (j=; j<i; ++j)

                 if (cal(i, j) && cal(j, i))

                     k++;

         printf("%d\n", k);

     }

     return ;

 }