Cod sursa(job #2417201)

Utilizator sichetpaulSichet Paul sichetpaul Data 29 aprilie 2019 10:42:20
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
#define DIM 120005
#define x first
#define y second
using namespace std;
int st1[DIM],st2[DIM];
pair<double,double> v[DIM];
double cross_product(int p0,int p1,int p2) {
   return (v[p1].x-v[p0].x)*(v[p2].y-v[p0].y)-(v[p2].x-v[p0].x)*(v[p1].y-v[p0].y);
}
int main()
{   int n,i;
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    f>>n;
    for (i=1;i<=n;++i)
        f>>v[i].x>>v[i].y;
    sort(v+1,v+n+1);

    int nr1=2;st1[1]=1,st1[2]=2;
    for (i=3;i<=n;++i) {
        while (nr1>=2 && cross_product(st1[nr1-1],st1[nr1],i)<0)
            --nr1;
        ++nr1,st1[nr1]=i;
    }

    int nr2=2;st2[1]=n,st2[2]=n-1;
    for (i=n-2;i>=1;--i) {
        while (nr2>=2 && cross_product(st2[nr2-1],st2[nr2],i)<0)
            --nr2;
        ++nr2,st2[nr2]=i;
    }

    g<<nr1+nr2-2<<'\n';
    for (i=1;i<=nr1;++i)
        g<<fixed<<setprecision(12)<<v[st1[i]].x<<" "<<v[st1[i]].y<<'\n';

    for (i=2;i<nr2;++i)
        g<<fixed<<setprecision(12)<<v[st2[i]].x<<" "<<v[st2[i]].y<<'\n';

    return 0;
}