Cod sursa(job #2953514)

Utilizator LuciBBadea Lucian LuciB Data 11 decembrie 2022 16:54:02
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>
using namespace std;

FILE *fin, *fout;

const int NMAX = 12e4;
const double EPS = 1e-12;


struct point {
	double x, y;
} v[NMAX];

vector<int> hull;

int findLowestPoint(int n) {
    double ymin = 1e9 + 1;
    int ind = -1;
    for(int i = 0; i < n; i++)
    	if(v[i].y < ymin) {
			ymin = v[i].y;
			ind = i;
    	}
	return ind;
}
/*
(b.y - a.y) / (b.x - a.x) ? (c.y - b.y) / (c.x - b.x)
*/

bool order(point a, point b, point c) {
	long double val1 = b.y - a.y;
	long double val2 = c.x - b.x;
	long double val3 = c.y - b.y;
	long double val4 = b.x - a.x;
    long double val = val1 * val2 - val3 * val4;
    return (val < 0);
}

bool cmp(point a, point b) {
    return order(v[0], a, b);
}

int main() {
    fin = fopen("infasuratoare.in", "r");
    fout = fopen("infasuratoare.out", "w");
    int n;
    fscanf(fin, "%d", &n);
    for(int i = 0; i < n; i++) {
		fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
    }
	swap(v[0], v[findLowestPoint(n)]);
    sort(v + 1, v + n, cmp);
    //for(int i = 0; i < n; i++)
    	//cout << v[i].x << ' ' << v[i].y << endl;
    hull.push_back(0);
    hull.push_back(1);
    hull.push_back(2);
    for(int i = 3; i < n; i++) {
		while(hull.size() >= 2 && !order(v[hull[hull.size() - 2]], v[hull[hull.size() - 1]], v[i]))
			hull.pop_back();
		hull.push_back(i);
    }
    fprintf(fout, "%d\n", hull.size());
    for(int i = 0; i < hull.size(); i++) {
		fprintf(fout, "%lf %lf\n", v[hull[i]].x, v[hull[i]].y);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}