Pagini recente » Cod sursa (job #658929) | Atasamentele paginii Profil hydrargyrum_ | Cod sursa (job #2019848) | Cod sursa (job #1602508) | Cod sursa (job #3353671)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;
struct elem{
double x, y;
};
bool comp( elem a, elem b ){
if( a.x != b.x ){
return a.x < b.x;
}
return a.y < b.y;
}
vector <elem> v, a, ras;
bool 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;
return p.y > exp_val;
}
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] ) == false ){
while( a.size() >= 2 && rel_to_line( a[a.size() - 1], a[a.size() - 2], v[i] ) == true ){
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] ) == true ){
while( a.size() >= 2 && rel_to_line( a[a.size() - 1], a[a.size() - 2], v[i] ) == false ){
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