Cod sursa(job #795702)

Utilizator tester9x9Tester9x9 tester9x9 Data 9 octombrie 2012 14:56:53
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.29 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#define INF 0x3f3f3f3f
#define NM 151000
#define x first
#define EPS 1e-12
#define y second
#define PID pair<double, double>
#define PTA pair< pair<double, double>, double >

using namespace std;


inline bool Equal (double a, double b)
{
    return (-EPS<(a-b) && (a-b)<EPS);
}

inline double Tang (const PID& A, const PID& B)
{
    if (Equal(A.x,B.x)) return INF;
    return 1.0*(A.y-B.y)/(A.x-B.x);
}

inline int Sign (const PID& P1, const PID& P2, const PID& P3)
{
    double S=P1.x*P2.y+P2.x*P3.y+P3.x*P1.y-P1.x*P3.y-P2.x*P1.y-P3.x*P2.y;
    if (Equal(S,0.0)) return 0;
    return (S<0?-1:1);
}

inline int Sign (const double& A, const double& B, const double& C, const PID& P)
{
    double S=A*P.x+B*P.y+C;
    if (Equal(S,0.0)) return 0;
    return (S<0?-1:1);
}

PID V[NM];

bool CCMP (const PID& A, const PID& B)
{
    return Tang(A,V[1])<Tang(B,V[1]);
}

int N,i,j;
int K;
PID S[NM];
PID P;
/*bool F[NM][NM];

vector< PTA > ANS;
vector< PTA >::iterator it;

bool Equalize (PTA a, PTA b)
{
    return (Equal(a.first.first,b.first.first) && Equal(a.first.second,b.first.second) && Equal(a.second,b.second))||(Equal(a.first.first,-b.first.first) && Equal(a.first.second,-b.first.second) && Equal(a.second,-b.second));
}

void GetEcM (const PID& P1, const PID& P2, double& A, double& B, double& C)
{
    if (Equal(P1.x,P2.x))
    {
        A=0;
        B=1;
        C=-(P1.y+P2.y)/2;
        return;
    }
    if (Equal(P1.y,P2.y))
    {
        A=1;
        B=0;
        C=-(P1.x+P2.x)/2;
        return;
    }


    double XM1, YM1, pant;
    double YM=(P1.y+P2.y)/2.0;
    double XM=(P1.x+P2.x)/2.0;
    pant = (P1.y - P2.y) / (P1.x - P2.x);
    pant = (-1) / pant;
    XM1 = XM - 1;
    YM1 = pant * XM1 - pant * XM + YM;
    A = YM - YM1;
    B = XM1 - XM;
    C = XM * YM1 - XM1 * YM;

    if (A<0)
    {
        A*=-1.0;
        B*=-1.0;
        C*=-1.0;
    }

    return;
}

int ZC;

int FL[NM];

void Solve (int P1, int P2, int T)
{
    F[P1][P2]=F[P2][P1]=1;

    double A,B,C;
    double sq;
    int sg;
    double D;
    double M1,M2;

    GetEcM(S[P1],S[P2],A,B,C);

    ++ZC;
    sq=sqrt(A*A+B*B);
    M1=1.0*A/sq;
    M2=1.0*B/sq;

    int i,j;
    bool ok;
    for (i=1; i<=N; i++)
        if (FL[i]!=ZC)
        {
            D=fabs(A*V[i].x+B*V[i].y+C)/sq;

            sg=Sign(A,B,C,V[i]);
            if (sg==0) continue;

            P.x=V[i].x-2.0*D*M1*sg;
            P.y=V[i].y-2.0*D*M2*sg;

            P.x-=EPS;
            P.y-=EPS;
            ok=0;
            j=(lower_bound(V+1,V+N+1,P)-V);
            P.x+=EPS;
            P.y+=EPS;
            for (; j<=N && (Equal(V[j].x,P.x) || Equal(V[j].x,P.x-EPS)); j++)
                if (i!=j && Equal(V[j].x,P.x) && Equal(V[j].y,P.y))
                {
                    ok=1;
                    FL[i]=FL[j]=ZC;
                    break;
                }
            if (ok==0) return;
        }

    ANS.push_back(make_pair(make_pair(A,B),C));
}*/

int main ()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d\n",&N);
    V[K=0].x=V[0].y=INF;

    for (i=1; i<=N; i++)
    {
        scanf("%lf %lf\n",&V[i].x,&V[i].y);
        if (V[i].x<V[K].x || (Equal(V[i].x,V[K].x) && V[i].y<V[K].y))
            K=i;
    }

    swap(V[1],V[K]);
    sort(V+2,V+N+1,CCMP);
    S[K=1]=V[1];

    for (i=2; i<=N; i++)
    {
        while (K>=2 && Sign(S[K-1],S[K],V[i])<=0) --K;
        S[++K]=V[i];
    }

    printf("%d\n",K);
    for (i=2; i<=K; i++)
        printf("%.12lf %.12lf\n",S[i].x,S[i].y);
    printf("%.12lf %.12lf\n",S[1].x,S[1].y);


    /*sort(V+1,V+N+1);

    for (i=1; i<=K; i++)
    {
        j=i+1;
        if (j>K) j-=K;

        if (!F[i][j]) Solve(i,j,0);

        j=i+2;
        if (j>K) j-=K;

        if (!F[i][j]) Solve(i,j,0);
    }

    sort(ANS.begin(),ANS.end());
    it=unique(ANS.begin(),ANS.end(),Equalize);
    ANS.resize(it-ANS.begin());

    printf("%d\n",ANS.size());

    for (i=0; i<ANS.size(); i++)
        printf("%.8lf %.8lf %.8lf\n",ANS[i].first.first,ANS[i].first.second,ANS[i].second);*/

    return 0;
}