Cod sursa(job #2571365)

Utilizator spartanul300Vasile Andrei spartanul300 Data 4 martie 2020 22:36:56
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
#define MAX_NR 1000000100

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct punct
{
    double x,y;
}v[120100],s[120100];

int compare(punct A,punct B)
{
    return ((A.x-v[1].x)*(B.y-v[1].y) > (A.y-v[1].y)*(B.x-v[1].x));
}

int viraj_dreapta(punct A, punct B, punct C)
{
    double val=((A.x*B.y)+(B.x*C.y)+(A.y*C.x))-(B.y*C.x+C.y*A.x+B.x*A.y);
    if(val<0)return 1;
    else if(val==0)return 0;
    else return -1;
}

int n,i,T,poz;
double minix=MAX_NR,miniy=MAX_NR;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>v[i].x>>v[i].y;
        if(v[i].x<minix)minix=v[i].x,miniy=v[i].y,poz=i;
        else if(v[i].x==minix)
            if(v[i].y<miniy)miniy=v[i].y,poz=i;
    }

    swap(v[1],v[poz]);
    sort(v+2,v+n+1,compare);

    T=2;
    s[1]=v[1];
    s[2]=v[2];

    for(i=3;i<=n;i++)
    {
        while(T>2 && viraj_dreapta(s[T-1],s[T],v[i])>=0)T--;
        T++;s[T]=v[i];
    }

    g<<T<<'\n';
    for(i=1;i<=T;i++)
        g<<fixed<<setprecision(6)<<s[i].x<<" "<<fixed<<setprecision(6)<<s[i].y<<'\n';

    return 0;
}