Cod sursa(job #3195704)

Utilizator ioanabaduIoana Badu ioanabadu Data 21 ianuarie 2024 15:36:01
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define N_MAX 150005

using namespace std;

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

struct point {double x, y;};

point points[N_MAX];
vector <point> ans;

int startingPoint (int n){
    int idx = 0;

    for (int i=1; i<n; ++i){
        if (points[i].x < points[idx].x || (points[i].x == points[idx].x && points[i].y < points[idx].y))
            idx = i;
    }

    return idx;
}

double orientation (point a, point b, point c){
    return (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
}

bool cmp (point a, point b){
    return orientation(points[0], a, b) < 0; // ordine trigonometrica
}

void findAns (int n){
    ans.push_back (points[0]);
    ans.push_back (points[1]);

    for (int i=2; i<n; ++i){
        while (ans.size() >= 2 && orientation(ans[ans.size() - 2], ans.back(), points[i]) >= 0)
            ans.pop_back();

        ans.push_back(points[i]);
    }
}

int main(){
    FILE *in, *out;

    in = fopen ("infasuratoare.in", "r");
    out = fopen ("infasuratoare.out", "w");

    int n;

    fscanf (in, "%d", &n);
    for (int i=0; i<n; ++i)
        fscanf (in, "%lf%lf", &points[i].x, &points[i].y);

    swap (points[0], points[startingPoint(n)]);

    sort (points + 1, points + n, cmp);

    findAns (n);

    fprintf (out, "%d \n", ans.size());
    for (point p:ans){
        fprintf (out, "%.12lf %.12lf \n", p.x, p.y);
    }
    return 0;
}