UVA 11928 The Busy Dog

题意：一只狗被拴在杆子上，从起点开始按直线依次跑到给出的点最后回到起点问绕杆子几圈，逆时针为正，顺时针为负，撞到杆子输出Ouch!。

解法：用叉积判断方向，用余弦定理求出以杆子为顶点的角，加和除以2π，最后的答案处理因为精度问题wa了一篇orz……

代码：

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string>

#include<string.h>

#include<math.h>

#include<limits.h>

#include<time.h>

#include<stdlib.h>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define LL long long

using namespace std;

const double eps = 1e-;

struct node

{

    double x, y;

} point[];

double cross(node p1, node p2, node p3)//叉积

{

    return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);

}

double len(node p1, node p2)//两点长度的平方

{

    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);

}

double cal(node p1, node p2, node p3)//余弦定理

{

    double a = len(p2, p3), b = len(p1, p3), c = len(p1, p2);

    return acos((b + c - a) / 2.0 / sqrt(b * c));

}

int line(node p1, node p2, node p3)//判断叉积为0时杆是否在两点中间

{

    return p3.x >= min(p1.x, p2.x) && p3.x <= max(p1.x, p2.x) && p3.y >= min(p1.y, p2.y) && p3.y <= max(p1.y, p2.y);

}

int main()

{

    int n;

    while(~scanf("%d", &n) && n)

    {

        node pole;

        scanf("%lf%lf", &pole.x, &pole.y);

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

            scanf("%lf%lf", &point[i].x, &point[i].y);

        double degree = 0.0;

        int ans = ;

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

        {

            double flag = cross(pole, point[i], point[i + ]);

            double res = cal(pole, point[i], point[i + ]);

            if((fabs(flag) <= eps) && line(point[i], point[i + ], pole))

            {

                ans = ;

                break;

            }

            else if(flag > eps)

                degree += res;

            else if(flag < -eps)

                degree -= res;

            else

            {

                if(line(point[i], point[i + ], pole))

                {

                    ans = ;

                    break;

                }

            }

        }

        double flag = cross(pole, point[n - ], point[]);

        double res = cal(pole, point[n - ], point[]);

        if((fabs(flag) <= eps) && line(point[n - ], point[], pole))

            ans = ;

        else if(flag > eps)

            degree += res;

        else if(flag < -eps)

            degree -= res;

        else if(line(point[n - ], point[], pole))

            ans = ;

        if(ans)

        {

            printf("Ouch!\n");

            continue;

        }

        degree = degree * 0.5 / acos(-1.0);

        char x[];

        sprintf(x, "%.0lf", degree);

        sscanf(x, "%d", &ans);

        if(ans > )

            printf("+");

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

    }

    return ;

}