Cod sursa(job #3353666)

Utilizator CosminaneBoac Mihai Cosmin Cosminane Data 9 mai 2026 12:43:16
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
struct elem{
	double x, y;
};
bool comp( elem a, elem b ){
	return a.x < b.x;
}
vector <elem> v, a, ras;
int rel_to_line( elem p, elem x, elem y ){
	double a, b, exp_val;
	a = ( x.y - y.y ) / ( x.x - y.x );
	b = x.y - a * x.x;
	exp_val = a * p.x + b;
	if( p.y == exp_val ){
		return 0;
	}
	if( p.y > exp_val ){
		return 1;
	}
	return -1;
}
int main(){
	int n, i;
	double x, y;
	ifstream fin( "infasuratoare.in" );
	ofstream fout( "infasuratoare.out" );
	fin >> n;
	for( i = 0; i < n; i++ ){
		fin >> x >> y;
		v.push_back( { x, y } );
	}
	sort( v.begin(), v.end(), comp );
	a.push_back( v[0] );
	for( i = 1; i < n - 1; i++ ){
		if( rel_to_line( v[i], v[i - 1], v[n - 1] ) == -1 ){
			while( a.size() >= 2 && rel_to_line( a[a.size() - 1], a[a.size() - 2], v[i] ) >= 0 ){
				a.pop_back();
			}
			a.push_back( v[i] );
		}
	}
	a.push_back( v[n - 1] );
	ras = a;
	a.clear();
	a.push_back( v[0] );
	for( i = 1; i < n - 1; i++ ){
		if( rel_to_line( v[i], v[i - 1], v[n - 1] ) == 1 ){
			while( a.size() >= 2 && rel_to_line( a[a.size() - 1], a[a.size() - 2], v[i] ) <= 0 ){
				a.pop_back();
			}
			a.push_back( v[i] );
		}
	}
	a.push_back( v[n - 1] );
	for( i = a.size() - 2; i >= 1; i-- ){
		ras.push_back( a[i] );
	}
	fout << ras.size() << '\n';
	for( i = 0; i < ras.size(); i++ ){
		fout << ras[i].x << ' ' << ras[i].y << '\n';
	}
	return 0;
}
// y1 = a * x1 + b
// y2 = a * x2 + b
// y1 - y2 = a * ( x1 - x2 )
// a = ( y1 - y2 ) / ( x1 - x2 )
// b = y1 - a * x1