Cod sursa(job #2953308)

Utilizator Teodor94Teodor Plop Teodor94 Data 10 decembrie 2022 22:17:18
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 120000

struct Point { double x, y; };

int noPoints;
Point points[MAX_N];
vector<Point> convexHull;

int findStartPoint() {
    int startIndex, i;

    startIndex = 0;
    for (i = 1; i < noPoints; ++i)
        if (points[i].y < points[startIndex].y ||
            (points[i].y == points[startIndex].y && points[i].x < points[startIndex].x))
            startIndex = i;
    
    return startIndex;
}

inline double orientation(const Point& a, const Point& b, const Point& c) {
    return (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
}

inline bool cmpPoint(const Point& a, const Point& b) {
    return orientation(points[0], a, b) < 0;
}

void computeHull() {
    int i;

    convexHull.push_back(points[0]);
    convexHull.push_back(points[1]);
    
    for (i = 2; i < noPoints; ++i) {
        while (convexHull.size() >= 2 && orientation(convexHull[convexHull.size() - 2], convexHull.back(), points[i]) >= 0)
            convexHull.pop_back();
        
        convexHull.push_back(points[i]);
    }
}

int main() {
    FILE *fin, *fout;
    fin = fopen("infasuratoare.in", "r");
    fout = fopen("infasuratoare.out", "w");

    int i;

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

    swap(points[0], points[findStartPoint()]);

    sort(points + 1, points + noPoints, cmpPoint);

    computeHull();

    fprintf(fout, "%llu\n", convexHull.size());
    for (const Point& p : convexHull)
        fprintf(fout, "%lf %lf\n", p.x, p.y);

    fclose(fin);
    fclose(fout);
    return 0;
}