学步园

判断一个多边形是否有核。

大体思想是，用多边形的边构成的直线，一点一点去削去原多边形。

蓝色区域则为多边形的核。

判断大于0还是小于0有一个小技巧：直线走向的左手边是小于0的，右手边是大于0的。

向量AB等于点B减去点A，走向为A指向B。

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
#define MAXN 2010
#define eps 1e-10
#define max(x, y) (x > y ? x : y)
#define min(x, y) (x < y ? x : y)
#define sig(x) ((x > eps) - (x < -eps))
#define cross(o, a, b) ((p[a] - p[o]) ^ (p[b] - p[o]))

const double pi = acos(-1.0);

typedef struct Point
{
        double x, y;
        Point() {}
        Point(double _x, double _y):
                x(_x), y(_y) {}
        bool operator <(const Point &argu) const
        {
            return sig(x - argu.x) == 0 ? y < argu.y : x < argu.x;
        }
        double dis(const Point &argu) const
        {
            return sqrt((x - argu.x) * (x - argu.x) + (y - argu.y) * (y - argu.y));
        }
        double dis2(const Point &argu) const
        {
            return (x - argu.x) * (x - argu.x) + (y - argu.y) * (y - argu.y);
        }
        double operator ^(const Point &argu) const
        {
            return x * argu.y - y * argu.x;
        }
        double operator *(const Point &argu) const
        {
            return x * argu.x + y * argu.y;
        }
        Point operator -(const Point &argu) const
        {
            return Point(x - argu.x, y - argu.y);
        }
        double len2() const
        {
            return x * x + y * y;
        }
        double len() const
        {
            return sqrt(x * x + y * y);
        }
        void in()
        {
            scanf("%lf%lf", &x, &y);
        }
        void out()
        {
            printf("%.3lf %.3lf\n", x, y);
        }
}Vector;

inline double Cross(const Point &o, const Point &a, const Point &b)
{
    return (a - o) ^ (b - o);
}

Point Get_Intersection(const Point &u1, const Point &u2, const Point &v1, const Point &v2)
{
    Point ret = u1;
    double t = ((u1.x - v1.x) * (v1.y - v2.y) - (u1.y-v1.y) * (v1.x - v2.x))
            / ((u1.x - u2.x) * (v1.y - v2.y) - (u1.y - u2.y) * (v1.x - v2.x));
    ret.x += (u2.x - u1.x) * t;
    ret.y += (u2.y - u1.y) * t;
    return ret;
}

Point Get_Intersection(const Point &x, const Point &y, double a, double b, double c)
{
    double u = fabs(a * x.x + b * x.y + c);
    double v = fabs(a * y.x + b * y.y + c);
    return Point((x.x * v + y.x * u) / (u + v), (x.y * v + y.y * u) / (u + v));
}

void Get_Line(const Point &x, const Point &y, double &a, double &b, double &c)
{
    a = y.y - x.y;
    b = x.x - y.x;
    c = y.x * x.y - x.x * y.y;
}

Point q[MAXN];
int Cut(Point p[], double a, double b, double c, int n)
{
    int cc = 0;
    for(int i = 1; i <= n; i++)
    {
        double k = a * p[i].x + b * p[i].y + c;
        if(sig(k) >= 0) q[++cc] = p[i];
        else
        {
            double k1 = a * p[i - 1].x + b * p[i - 1].y + c;
            double k2 = a * p[i + 1].x + b * p[i + 1].y + c;
            if(k1 > 0) q[++cc] = Get_Intersection(p[i], p[i - 1], a, b, c);
            if(k2 > 0) q[++cc] = Get_Intersection(p[i], p[i + 1], a, b, c);
        }
    }
    for(int i = 1; i <= cc; i++) p[i] = q[i];
    p[cc + 1] = q[1], p[0] = p[cc];
    return cc;
}

int solve(Point pp[], Point ke[], int n)
{
    int cc = n;
    for(int i = 1; i <= n; i++)
    {
        double a, b, c;
        Get_Line(pp[i], pp[i + 1], a, b, c);
        cc = Cut(ke, a, b, c, cc);
    }
    if(cc >  0) return 0;
    if(cc <= 0) return 1;
}

char ans[2][30] = {
    "Surveillance is possible.",
    "Surveillance is impossible." };
Point pp[MAXN], ke[MAXN];
int n;

int main()
{
//    freopen("J.in", "r", stdin);

    int cas = 1;
    while(scanf("%d", &n) && n)
    {
        for(int i = 1; i <= n; i++) pp[i].in(), ke[i] = pp[i];
        ke[n + 1] = pp[n + 1] = pp[1];
        ke[0] = pp[0] = pp[n];
        printf("Floor #%d\n%s\n\n", cas++, ans[solve(pp, ke, n)]);
    }
    return 0;
}