Cod sursa(job #2935444)

Utilizator gabriela.stanStan Luciana-Gabriela gabriela.stan Data 6 noiembrie 2022 18:56:58
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>
#define NMAX 120001

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int n;

enum Orientare
{
    CLOCKWISE, 
    COUNTERCW,
    COLINIARE
};

struct Point
{
    long double x, y;
}p[NMAX];

Orientare orientare(Point A, Point B, Point C)
{
    long double det=(A.y-B.y)*(C.x-B.x)-(A.x-B.x)*(C.y -B.y);
    if(det<0) return CLOCKWISE;
    if(det>0) return COUNTERCW;
    return COLINIARE;
}

bool comp(Point Pi, Point Pj)
{
    if(orientare(p[0], Pi, Pj)==CLOCKWISE) return 0;
    if(orientare(p[0], Pi, Pj)==COLINIARE)
    {
        if(Pi.x>Pj.x) return 0;
        if(Pi.x==Pj.x && abs(p[0].y-Pi.y)>abs(p[0].y-Pj.y)) return 0;
    }
    return 1;
}

vector <Point> v;
void poligon()
{
    v.push_back(p[0]);
    v.push_back(p[1]);
    for(int i=2; i<n; i++)
    {
        int s=v.size()-1;
        while(s>1 && orientare(v[s-1], v[s], p[i])==CLOCKWISE)
        {
            v.pop_back();
            s--;
        }
        v.push_back(p[i]);
    }
}

int main()
{
    fin>>n;
    for(int i=0; i<n; i++) 
    {
        fin>>p[i].x>>p[i].y;
        if(p[0].x>p[i].x)
        {
            swap(p[0], p[i]);
        }
        else if(p[0].x==p[i].x)
        {
            if(p[0].y>p[i].y) swap(p[0], p[i]);
        }
    }
    cout<<p[0].x<<" "<<p[0].y;
    sort(p+1, p+n, comp);
    //for(int i=0; i<n; i++) fout<<p[i].x<<" "<<p[i].y<<'\n';
    poligon();
    fout<<v.size()<<'\n';
    for(auto & i:v)
    {
        fout<<fixed<<setprecision(6)<<i.x<<" ";
        fout<<fixed<<setprecision(6)<<i.y<<'\n';
    }
}