Cod sursa(job #2281903)

Utilizator oloeriudeliaOloeriu Delia Ioana oloeriudelia Data 12 noiembrie 2018 22:04:58
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <fstream>
#include <algorithm>
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, poz;
double auxx, auxy;
struct punct{double x, y;}A[120005], P0, s[120005];
double cp(punct A, punct B, punct P0)
{
    return (A.x-P0.x)*(B.y-P0.y)-(B.x-P0.x)*(A.y-P0.y);
}
bool comp(punct A, punct B)
{
    if(cp(A, B, P0)>0) return 1;
    if(cp(A, B, P0)<0) return 0;
    if(A.x*A.x+A.y*A.y < B.x*B.x+B.y*B.y) return 1;
    return 0;
}
int main()
{
    fin>>n;
    fin>>P0.x>>P0.y;
    A[1].x=P0.x, A[1].y=P0.y;
    for(int i=2;i<=n;++i)
    {
        fin>>A[i].x>>A[i].y;
        if(A[i].x<P0.x)
            {
                P0.x=A[i].x;
                P0.y=A[i].y;
                poz=i;
            }
        else
        {
            if(A[i].x==P0.x && A[i].y<P0.y)
                {
                P0.x=A[i].x;
                P0.y=A[i].y;
                poz=i;
            }
        }
    }
    //fout<<P0.x<<' '<<P0.y;
    swap(A[1], A[poz]);
    sort(A+2, A+n+1, comp);
    s[1]=A[1];
    s[2]=A[2];
    int vf1=2, vf2=1, nr=2;
    int i=3;
    while(nr>=2)
    {
        if(cp(s[vf2], s[vf1], A[i])>0)
        {
            if(i==n+1)
                {break;}
            else
            {
                s[++nr]=A[i];
                ++vf1;
                ++vf2;
                ++i;
            }
        }
        else
        {
            s[nr].x=0;
            s[nr].y=0;
            --nr;
            --vf1;
            --vf2;
        }
    }
    fout<<nr<<'\n';
    for(int i=2;i<=nr;++i)
        fout<<setprecision(12)<<fixed<<s[i].x<<' '<<s[i].y<<'\n';
    fout<<s[1].x<<' '<<s[1].y;
    return 0;
}