Cod sursa(job #2538028)

Utilizator ionut.birisBiris Ionut ionut.biris Data 4 februarie 2020 12:00:58
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;

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

const int NMAX = 120000;

struct Point{
float x,y;} X[NMAX];

int N;
int S1[NMAX],cnt;
int S2[NMAX],cnt2;
bool in[NMAX];

void read(){
    f >> N;
    for(int i = 1; i <= N;i++)
        f >> X[i].x >> X[i].y;
}

int Orientare(Point a, Point b, Point c){
    int rez = (a.x*b.y) + (b.x*c.y) +(c.x*a.y) - (b.y*c.x) - (c.y*a.x) - (a.y*b.x);
    if (rez <0) return -1;
    if(rez>0) return 1;
    return 0;
}

void swapp(Point &a, Point &b){
    Point t = a;
    a = b;
    b = t;
}

void Sort(){
    for(int i = 1; i <= N;i++)
        for(int j = i+ 1; j <= N;j++){
            if(X[i].y > X[j].y)
                swapp(X[i],X[j]);
            else if(X[i].y == X[j].y)
                if(X[i].x > X[j].x)
                    swapp(X[i],X[j]);
        }
}

void ConvexHull(){
    S1[1] = 1;
    in[S1[1]] = true;
    S1[2] = 2;
    in[S1[2]] = true;
    cnt = 2;

    for(int i = 3; i <= N;i++){
            while(Orientare(X[S1[cnt]],X[S1[cnt-1]],X[i]) > 0){
                in[S1[cnt]] = false;
                cnt--;
            }
    S1[++cnt] = i;
    in[S1[cnt]] = true;

    }

    S2[1] = 1;
    S2[2] = 2;
    cnt2 = 2;
    for(int i = 3; i <= N;i++){
        while(Orientare(X[S2[cnt2]],  X[S2[cnt2-1]],  X[i]) < 0 )
            cnt2--;
    S2[++cnt2] = i;
    }
}

void Legare(){
   for(int i = cnt2; i >= 1;i--){
        if(!in[S2[i]])
            S1[++cnt] = S2[i];
   }
}

int main()
{
    read();
    Sort();
    ConvexHull();
    Legare();
    g << cnt << "\n";
    g << fixed << showpoint << setprecision(6);
    for(int i = 1; i <= cnt;i++)
        g << setprecision(6) << X[S1[i]].x << " " << setprecision(6) << X[S1[i]].y << "\n";
    return 0;
}