Cod sursa(job #2473793)

Utilizator AdryanR8iurian adrian razvan AdryanR8 Data 14 octombrie 2019 11:53:48
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;

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

struct PUNCT{
    double x=0.0;
    double y=0.0;
};

vector <PUNCT> V;

int n,k;
PUNCT P[201];
PUNCT S[201];

double dist(PUNCT A, PUNCT B){
    return sqrt((double)(A.x-B.x)*(double)(A.x-B.x)+(double)(A.y-B.y)*(double)(A.y-B.y));
}

int cmp(PUNCT A,PUNCT B){
    if (A.y<B.y)
        return 1;
    if (A.y>B.y)
        return 0;
    if (A.x<B.x)
        return 1;
    return 0;
}

int stanga(PUNCT A, PUNCT B, PUNCT C){
    A.x-=B.x;
    A.y-=B.y;
    C.x-=B.x;
    C.y-=B.y;
    int pv=A.x*C.y-A.y*C.x;
    if (pv<0)
        return 1;
    return 0;
}

int main()
{
    in>>n;
    for (int i=1;i<=n;i++)
        in>>P[i].x>>P[i].y;
    sort(P+1,P+n+1,cmp);

    for (int i=1;i<=n;)
        if (k<=1)
            S[++k]=P[i++];
        else
            if (stanga(P[i],S[k-1],S[k]))
                S[++k]=P[i++];
            else
                k--;
    for(int i=1;i<=k;i++)
        V.push_back(S[i]);
    k=0;
    for(int i=n;i>=1;)
        if (k<=1)
            S[++k]=P[i--];
        else
            if (stanga(P[i],S[k-1],S[k]))
                S[++k]=P[i--];
            else
                k--;
    out << k+V.size()-2 << "\n";
    for(int i=0;i<V.size();i++)
        out << setprecision(6) << fixed << V[i].x << " " << V[i].y << "\n";
    for(int i=2;i<k;i++)
        out << setprecision(6) << fixed << S[i].x << " " << S[i].y << "\n";
    return 0;
}