Cod sursa(job #2882210)

Utilizator dp_flowRadu Radu dp_flow Data 31 martie 2022 11:14:46
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define NMax 120
#define CMax 1200000
#define Point pair<double,double>
#define mp make_pair

Point S = mp(CMax, CMax);

bool comparator(const Point& p1, const Point& p2) {
    double x1, y1, x2, y2, x3, y3;
    x1 = S.first; y1 = S.second;
    x2 = p1.first; y2 = p1.second;
    x3 = p2.first; y3 = p2.second;

    return (y2 - y1) * (x3 - x1) - (y3 - y1) * (x2 - x1) >= 1e-12;
}

bool ccw(Point &p1, Point &p2, Point &p3) {
    double x1, y1, x2, y2, x3, y3;
    x1 = p1.first; y1 = p1.second;
    x2 = p2.first; y2 = p2.second;
    x3 = p3.first; y3 = p3.second;

    return (y2 - y1) * (x3 - x1) - (y3 - y1) * (x2 - x1) < 1e-12;   
}

int N;
vector<Point> points;

int main() {
    freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);

    scanf("%d", &N);

    int index = -1;
    points.push_back(mp(CMax,CMax));

    for(int i = 1; i <= N; i++) {
        double x, y;
        scanf("%lf %lf", &x, &y);
        points.push_back(mp(x, y));
        if(y < S.second) {
            S = mp(x, y);
            index = i;
        }
        else if(abs(y - S.second) < 1e-12) {
            if(x < S.first) {
                S = mp(x, y);
                index = i;
            }
        }
    }
    
    swap(points[1], points[index]);
    sort(points.begin() + 2, points.end(), comparator);

    Point st[N + 2];
    st[1] = points[1];
    st[2] = points[2];
    int k = 2;

    for(int i = 3; i <= N; i++) {
        k++;
        st[k] = points[i];
        while(k >= 3 && ccw(st[k - 2], st[k - 1], st[k])) {
            st[k - 1] = st[k];
            k--;
        }
    }

    printf("%d\n", k);
    printf("%lf %lf\n", S.first, S.second);
    for(int i = k; i >= 2; i--) {
        printf("%lf %lf\n", st[i].first, st[i].second);
    }
    return 0;
}