Pagini recente » Borderou de evaluare (job #3366830) | Monitorul de evaluare | Borderou de evaluare (job #3366059) | Borderou de evaluare (job #3365399) | Cod sursa (job #3366945)
#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