Cod sursa(job #2682245)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 8 decembrie 2020 11:31:29
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <cstdio>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

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

const int N = 120000;

struct punct{
    double x, y;
} coords[N];


bool cmp(punct a, punct b){
    if(a.y < b.y)
        return true;
    if(a.y == b.y && a.x < b.x)
        return true;
    return false;
}

double getArea(punct p1, punct p2, punct p3){
    double area = p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);
    return area;
}

vector <punct> stiva1;
vector <punct> stiva2;

int main()
{
    int n, i, top1, top2;
    double area;
    fin >> n;
    for(i = 0; i < n; i++)
        fin >> coords[i].x >> coords[i].y;
    sort(coords, coords + n, cmp);

    stiva1.push_back(coords[0]);
    stiva2.push_back(coords[0]);

    for(i = 1; i < n; i++){
        area = getArea(coords[0], coords[n - 1], coords[i]);
        if(area >= 0){
            top1 = (int)stiva1.size();
            while(top1 > 1 && getArea(stiva1[top1 - 2], stiva1[top1 - 1], coords[i]) >= 0){
                stiva1.pop_back();
                top1--;
            }
            stiva1.push_back(coords[i]);
        }
        if(area <= 0){
            top2 = (int)stiva2.size();
            while(top2 > 1 && getArea(stiva2[top2 - 2], stiva2[top2 - 1], coords[i]) <= 0){
                stiva2.pop_back();
                top2--;
            }
            stiva2.push_back(coords[i]);
        }
    }

    top1 = (int)stiva1.size();
    top2 = (int)stiva2.size();
    fout << top1 + top2 - 2 << "\n";
    fout << setprecision(6) << fixed;

    for(i = 0; i < top2; i++)
        fout << stiva2[i].x << " " << stiva2[i].y << "\n";
    for(i = top1 - 2; i > 0; i--)
        fout << stiva1[i].x << " " << stiva1[i].y << "\n";
    return 0;
}