Pagini recente » Cod sursa (job #990908) | Cod sursa (job #989274) | Cod sursa (job #829446) | Cod sursa (job #1780686) | Cod sursa (job #3353667)
#include <fstream>
#include <algorithm>
#include <iomanip>
#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';
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