Cod sursa(job #3366945)

Utilizator CosminaneBoac Mihai Cosmin Cosminane Data 5 octombrie 2026 13:10:54
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;
struct elem{
	double x, y;
};
vector <elem> v, ras;
elem p;
int det( elem a, elem b, elem c ){
	double r;
	r = a.x * ( b.y - c.y ) + b.x * ( c.y - a.y ) + c.x * ( a.y - b.y );
	if( r < 0 ){
		return 1;
	}
	if( r > 0 ){
		return -1;
	}
	return 0;
}
bool comp( elem a, elem b ){
	int d;
	//cout << "AJUNS\n";
	d = det( p, a, b );
	//cout << a.x << ' ' << a.y << ' ' << b.x << ' ' << b.y << ' ' << d << ' ';
	if( d == 0 ){
		//cout << ( ( p.x - a.x ) * ( p.x - a.x ) + ( p.y - a.y ) * ( p.y - a.y ) < ( p.x - b.x ) * ( p.x - b.x ) + ( p.y - b.y ) * ( p.y - b.y ) ) << '\n';
		return ( ( p.x - a.x ) * ( p.x - a.x ) + ( p.y - a.y ) * ( p.y - a.y ) < ( p.x - b.x ) * ( p.x - b.x ) + ( p.y - b.y ) * ( p.y - b.y ) );
	}
	//cout << ( d < 0 ) << '\n';
	return ( d < 0 );
}
int main(){
	int n, i;
	double x, y;
	ifstream fin( "infasuratoare.in" );
	ofstream fout( "infasuratoare.out" );
	fin >> n;
	p = { INT32_MAX, INT32_MAX };
	for( i = 0; i < n; i++ ){
		fin >> x >> y;
		v.push_back( { x, y } );
		if( x < p.x || ( x == p.x && y < p.y ) ){
			p = v.back();
		}
	}
	//cout << "AJUNS1\n";
	sort( v.begin(), v.end(), comp );
	//cout << "AJUNS2\n";
	ras.push_back( p );
	ras.push_back( v[1] );
	for( i = 2; i < v.size(); i++ ){
		//cout << ras[ras.size() - 2].x << ' ' << ras[ras.size() - 2].y << ' ' << ras.back().x << ' ' << ras.back().y << ' ' << v[i].x << ' ' << v[i].y << ' ' << det( ras[ras.size() - 2], ras.back(), v[i] ) << '\n';
		while( ras.size() >= 2 && det( ras[ras.size() - 2], ras.back(), v[i] ) > 0 ){
			ras.pop_back();
		}
		ras.push_back( v[i] );
	}
	fout << ras.size() << '\n';
	fout << setprecision( 6 ) << fixed;
	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