Cod sursa(job #3265357)

Utilizator rARES_4Popa Rares rARES_4 Data 29 decembrie 2024 18:28:04
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
 #include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include<vector>
#include<iomanip>
using namespace std;

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

struct coordonate{
double x = 2000;
double y = 2000;
int i;
};

int n, x, y;
coordonate ppunct, coord[101], rez[101];

vector <int> v;

double det(double p1x, double p1y, double p2x, double p2y, double p3x, double p3y)
{
    return (p1x*p2y)+(p3x*p1y)+(p2x*p3y)-(p2y*p3x)-(p1y*p2x)-(p1x*p3y);
}

bool sortare_det(coordonate coordA, coordonate coordB)
{
    int detA;
    detA = det(ppunct.x, ppunct.y, coordA.x, coordA.y, coordB.x, coordB.y);
    if(detA > 0) return 1;
    else return 0;
}

int main()
{
    f>>n;
    for(int i = 1; i<=n; i++)
    {
        f>>coord[i].x>>coord[i].y;
        if(coord[i].x <= ppunct.x && coord[i].y <= ppunct.y)
        {
            ppunct.x = coord[i].x;
            ppunct.y = coord[i].y;
            ppunct.i = i;
        }
    }
    swap(coord[ppunct.i], coord[1]);
    sort(coord+2, coord+n+1, sortare_det);
    v.push_back(1);
    v.push_back(2);
    for(int i = 3; i<=n; i++)
    {
        int x = v.size();
        int c1 = v[x-2], c2 = v[x-1];
        double detA;
        detA = det(coord[c1].x, coord[c1].y, coord[c2].x, coord[c2].y, coord[i].x, coord[i].y);
        while(v.size() > 1 && detA < 0)
        {
            v.pop_back();
            x--;
            if(v.size() <= 1) break;
            c1 = v[x-2], c2 = v[x-1];
            detA = det(coord[c1].x, coord[c1].y, coord[c2].x, coord[c2].y, coord[i].x, coord[i].y);
        }
        v.push_back(i);
    }
    d<<v.size()<<'\n';
    for(auto x:v)
    {
        d<<fixed << setprecision(6) << coord[x].x<<' '<<coord[x].y<<'\n';
    }
}