Mai intai trebuie sa te autentifici.

Cod sursa(job #2556966)

Utilizator PandaChanTrusca Daria PandaChan Data 25 februarie 2020 13:19:06
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include<bits/stdc++.h>
#define NMAX 120010
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
int inceput;
struct punct{
    double x, y;
}puncte[NMAX], s[NMAX];
void citire()
{
    f>>n;
    for(int i=1; i<=n; i++)
        f>>puncte[i].x>>puncte[i].y;
}
double orientare(punct a, punct b, punct c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(punct a, punct b)
{
    return (orientare(puncte[1], a, b)<0);
}
void sortare2()
{
    for(int i=2; i<n; i++)
        for(int j=i+1; j<=n; j++)
            if(cmp(puncte[i], puncte[j]))
                swap(puncte[i], puncte[j]);
}
void sortare()
{
    int poz=1;
    for(int i=2; i<=n; i++)
        if(cmp(puncte[i], puncte[poz]))
            poz=i;
    swap(puncte[1], puncte[poz]);
    sortare2();
}
void prelucrare()
{
    s[1]=puncte[1];
    s[2]=puncte[2];
    inceput=2;
    for(int i=3; i<=n; i++)
    {
        while(inceput>=2 && orientare(s[inceput-1], s[inceput], puncte[i])<0)
            inceput--;
        inceput++;
        s[inceput]=puncte[i];
    }
}
void afisare()
{
    g<<inceput<<'\n';
    for(int i=1; i<=inceput; i++)
        g<<fixed<<setprecision(9)<<s[i].x<<' '<<s[i].y<<'\n';
}
int main()
{
    citire();
    sortare();
    prelucrare();
    afisare();
    return 0;
}