Cod sursa(job #2538304)

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

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

const int NMAX = 120005;

struct Point{
double 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 && cnt > 1){
                in[S1[cnt]] = false;
                cnt--;
            }
    S1[++cnt] = i;
    in[S1[cnt]] = true;

    }

    S2[1] = 8;
    S2[2] = 7;
    cnt2 = 2;
    for(int i = N-2; i >= 1;i--){
        while(Orientare(X[S2[cnt2]],  X[S2[cnt2-1]],  X[i]) > 0 && cnt2 > 1){
            in[S2[cnt]] = false;
            cnt2--;
        }
    S2[++cnt2] = i;
    in[S2[cnt]] = true;
    }

}

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

int main()
{
    read();
    Sort();
    ConvexHull();

    Legare();
    g << cnt << "\n";

    for(int i = 1; i <= cnt;i++)
        g  << X[S1[i]].x << " "  << X[S1[i]].y << "\n";

    return 0;
}