Pagini recente » Cod sursa (job #2792738) | Cod sursa (job #1255915) | Cod sursa (job #522543) | Cod sursa (job #270367) | Cod sursa (job #2468925)
#include<bits/stdc++.h>
using namespace std;
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
struct puncte {
double x;
double y;
} v[100000], stiva[100000];
bool cmp1( puncte a, puncte b ) {
if ( a.y == b.y )
return a.x < b.x;
else
return a.y < b.y;
}
bool cmp2( puncte a, puncte b ) {
return atan2( a.y - v[0].y, a.x - v[0].x ) < atan2( b.y - v[0].y, b.x - v[0].x );
}
int main() {
int n, i, poz;
fin >> n;
for ( i = 0; i < n; i++ )
fin >> v[i].x >> v[i].y;
sort( v, v + n, cmp1 );
sort( v + 1, v + n, cmp2 );
stiva[0] = v[0];
stiva[1] = v[1];
poz = 2;
for ( i = 2; i < n; i++ ) {
while ( poz >= 2 && (stiva[poz - 1].y - stiva[poz - 2].y) * (v[i].x - stiva[poz - 1].x) > (v[i].y - stiva[poz - 1].y) * (stiva[poz - 1].x - stiva[poz - 2].x) )
poz--;
stiva[poz] = v[i];
poz++;
}
fout << poz << "\n";
for ( i = 0; i < poz; i++ )
fout << setprecision(6) << fixed << stiva[i].x << " " << stiva[i].y << "\n";
return 0;
}