Pagini recente » Cod sursa (job #956594) | Cod sursa (job #48427) | Cod sursa (job #99848) | Cod sursa (job #408480) | Cod sursa (job #2531654)
#include <fstream>
#include <deque>
#include <algorithm>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct Punct
{
long double x, y;
};
deque < Punct > H;
Punct v[120005], vv[120005], Inceput;
int n;
void citire_si_gasirea_primelor_2_puncte();
bool crt ( Punct a, Punct b );
bool triunghi_in_sens_trigonometric ( Punct a, Punct b, Punct c );
int main()
{
Punct prec1, prec2;
int i;
citire_si_gasirea_primelor_2_puncte();
prec1 = H.front();
prec2 = Inceput;
for ( i = 1 ; i <= n ; i++ )
{
while ( triunghi_in_sens_trigonometric ( prec2, prec1, v[i] ) == 0 )
{
H.pop_front();
prec1 = prec2;
H.pop_front();
prec2 = H.front();
H.push_front ( prec1 );
}
prec2 = prec1;
prec1 = v[i];
H.push_front ( v[i] );
}
fout << H.size() << '\n';
while ( H.empty() == 0 ) fout << H.back().x << ' ' << H.back().y << '\n', H.pop_back();
return 0;
}
void citire_si_gasirea_primelor_2_puncte()
{
Punct x;
int i, j;
fin >> n >> v[1].x >> v[1].y;
j = 1;
for ( i = 2 ; i <= n ; i++ )
{
fin >> v[i].x >> v[i].y;
if ( v[i].x < v[j].x || ( v[i].x == v[j].x && v[i].y < v[j].y ) ) j = i;
}
Inceput = v[j];
for ( i = j ; i < n ; i++ ) v[i] = v[i+1];
n--;
sort ( v + 1, v + n + 1, crt );
v[0] = v[n];
v[n+1] = v[1];
v[n+2].x = v[n+2].y = 1000000001;
j = n + 2;
for ( i = 1 ; i <= n ; i++ ) if ( triunghi_in_sens_trigonometric ( Inceput, v[i], v[i-1] ) == 1 && triunghi_in_sens_trigonometric ( Inceput, v[i], v[i-1] ) == 1 ) if ( v[i].x < v[j].x || ( v[i].x == v[j].x && v[i].y < v[j].y ) ) j = i;
for ( i = j ; i <= n ; i++ ) vv[i-j+1] = v[i];
for ( i = 1 ; i < j ; i++ ) vv[i+n-j] = v[i];
for ( i = 1 ; i <= n ; i++ ) v[i] = vv[i];
for ( i = 1; i < n ; i++ ) v[i] = v[i+1];
n--;
H.push_front ( Inceput );
H.push_front ( vv[1] );
}
bool crt ( Punct a, Punct b )
{
if ( triunghi_in_sens_trigonometric ( Inceput, a, b ) == 1 ) return 1;
return 0;
}
bool triunghi_in_sens_trigonometric ( Punct a, Punct b, Punct c )
{
b.x -= a.x;
b.y -= a.y;
c.x -= a.x;
c.y -= a.y;
if ( b.x * c.y - b.y * c.x < 0 ) return 0;
return 1;
}