Cod sursa(job #2262619)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 17 octombrie 2018 17:27:09
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define DIM 120010
using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
int n,i,k,d[DIM];
double nr1,nr2;
struct punct {
    double x;
    double y;
};
punct v[DIM];
int cmp2 (punct a, punct b){
    if (a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}
int cadran (punct a){
    if (a.x >= 0 && a.y >= 0)
        return 1;
    return 2;
}
int cmp (punct a, punct b){

    if (cadran(a) != cadran (b))
        return cadran (a) < cadran (b);

    if (a.x*b.y - b.x*a.y != 0)
        return a.x*b.y - b.x*a.y > 0;

    return (a.x*a.x + a.y*a.y) < (b.x*b.x + b.y*b.y);

}
int verif (punct a, punct b, punct c){

    if ( (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x) <=0 )
        return 1;
    return 0;

}
int main (){

    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;
    sort (v+1,v+n+1,cmp2);
    /// normalizare
    nr1 = v[1].x, nr2 = v[1].y;
    for (i=1;i<=n;i++)
        v[i].x -= nr1, v[i].y -= nr2;

    /// sortare unghi
    sort (v+1,v+n+1,cmp);

    d[1] = 1;
    d[2] = 2;
    k = 2;
    for (i=3;i<=n;i++){
        while (k >= 2 && verif (v[d[k-1]],v[d[k]],v[i]))
            k--;
        d[++k] = i;
    }
    fout<<k<<"\n";
    for (i=1;i<=k;i++)
        fout<<setprecision(6)<<fixed<<v[d[i]].x + nr1<<" "<<v[d[i]].y + nr2<<"\n";

    return 0;
}