2015年2月16日 星期一

2015/02/16 vijos P1920 校园足迹

// https://vijos.org/p/1920
#include <iostream>
#include <cstdio>

using namespace std;

#define eps 1e-8

int N;
double X[500], Y[500];

bool same(int a, int b)
{
    if( X[a]-eps < X[b] && X[b] < X[a]+eps )
        if( Y[a]-eps < Y[b] && Y[b] < Y[a]+eps )
            return true;

    return false;
}

int main()
{
    scanf("%d", &N);

    for(int Ni = 0; Ni < N; Ni++)
        scanf("%lf %lf", &X[Ni], &Y[Ni]);

    int Ans = 0;

    for(int Ni = 0; Ni < N; Ni++)
        for(int Nj = Ni+1; Nj < N; Nj++)
        {
            if( same(Ni, Nj) ) continue;

            bool OK = true;

            for(int Nk = 0; Nk < N; Nk++)
            {
                if( Nk == Ni || Nk == Nj ) continue;

                if( same(Ni, Nk) )
                {
                    if( Nk < Ni ) OK = false;
                    else continue;
                }
                if( same(Nj, Nk) )
                {
                    if( Nk < Nj ) OK = false;
                    else continue;
                }

                double x1 = (X[Nj]-X[Ni]);
                double y1 = (Y[Nj]-Y[Ni]);

                double x2 = (X[Nk]-X[Ni]);
                double y2 = (Y[Nk]-Y[Ni]);

                double p = x1*y2-x2*y1;

                if( -eps < p && p < eps )
                {
                    double d1 = x1*x1+y1*y1;
                    double d2 = x1*x2+y1*y2;

                    if( d2 > eps && d2 < d1-eps )
                    {
                        OK = false;
                    }
                }
            }


            if( OK ) Ans+=2;

        }

    printf("%d\n", Ans);
}

沒有留言:

張貼留言