Cod sursa(job #3166517)

Utilizator maiaauUngureanu Maia maiaau Data 8 noiembrie 2023 21:29:58
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
using namespace std;
typedef pair<double, double> pt;
#define x first
#define y second 
#define pb push_back

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

const int N = 12e4+3;

int n, r[N];
pt v[N];

double det(pt,pt,pt);
bool sorttrig(pt,pt);
void read();

int main()
{
	read();
	sort(v+1, v+n, sorttrig); 
	int k = 1; r[1] = 1;
	for (int i = 2; i < n; i++){
		while (k > 1 && det(v[r[k-1]], v[r[k]], v[i])<=0) k--;
		k++; r[k] = i;
	}
	g << k+1 << '\n' << fixed << setprecision(12);
	for (int i = 0; i <= k; i++)
		g << v[r[i]].x << ' ' << v[r[i]].y << '\n';

	return 0;
}

void read(){
	f >> n;
	for (int i = 0; i < n; i++) 
		f >> v[i].x >> v[i].y;
	int j = 0;
	for (int i = 1; i < n; i++)
		if (v[i] < v[j]) j = i;
	swap(v[j], v[0]);
}
double det(pt a, pt b, pt c){
	return (a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x);
}
bool sorttrig(pt a, pt b){
	return det(v[0], a, b) > 0;
}