Pagini recente » Cod sursa (job #319436) | Cod sursa (job #2966711) | Cod sursa (job #1322704) | Cod sursa (job #425385) | Cod sursa (job #2532534)
#include <bits/stdc++.h>
#define Dmax 1000000005
using namespace std;
ifstream fin ( "infasuratoare.in" );
ofstream fout ( "infasuratoare.out" );
struct Point
{
double x, y;
friend bool operator < ( Point a, Point b );
};
vector < Point > s;
vector < Point > v;
Point refPoint;
int n, lng, imin;
void read ( );
void Infasuratoare ( );
bool Arie ( Point a );
int main ( )
{
read ( );
sort ( v.begin(), v.end() );
/*for ( int i = 0; i < n; i++ )
fout << v[i].x << ' '<< v[i].y << '\n';
fout << "\n\n\n\n";*/
Infasuratoare ( );
fout << lng+1 << '\n';
setprecision(15);
for ( int i = imin; i <= lng; i++ )
fout << fixed << s[i].x << ' ' << s[i].y << '\n';
for ( int i = 0; i < imin; i++ )
fout << fixed << s[i].x << ' ' << s[i].y << '\n';
}
bool Arie ( Point c )
{
Point a, b;
vector < Point > :: iterator it;
it = s.end();
--it;
b = *it;
a = *(--it);
double det =( a.x*b.y + a.y*c.x + c.y*b.x ) - ( b.y*c.x + c.y*a.x + a.y*b.x );
if ( det > 0 )
return 1;
else if ( det < 0 )
return 0;
else
{
bool sens = 0;
if ( b.x > a.x || b.y > a.y )
sens = 1;
if ( sens == 0 )
{
if ( c.x < b.x || c.y < b.y )
return 1;
return 0;
}
else
{
if ( c.x > b.x || c.y > b.y )
return 1;
return 0;
}
}
}
void Infasuratoare ( )
{
s.push_back ( v[0] );
s.push_back ( v[1] );
stack < int > sol;
lng = 1;
if ( v[0].y < v[1].y )
sol.push(0);
else if ( v[0].y > v[1].y )
sol.push(1);
else if ( v[0].x < v[1].x )
sol.push(0);
else
sol.push(1);
for ( int i = 2; i < n; i++ )
{
if ( Arie ( v[i] ) == 0 )
{
s.erase ( --s.end() );
i--;
if ( lng == sol.top() )
sol.pop( );
lng--;
}
else
{
lng++;
s.push_back ( v[i] );
if ( s[lng].y < s[sol.top()].y )
sol.push(lng);
else if ( s[lng].y == s[sol.top()].y && s[lng].x < v[sol.top()].x )
sol.push(lng);
}
}
imin = sol.top();
}
void read ( )
{
refPoint.x = Dmax;
refPoint.y = Dmax;
Point p;
fin >> n;
for ( int i = 1; i <= n; i++ )
{
fin >> p.x >> p.y;
v.push_back ( p );
if ( p.x < refPoint.x )
refPoint = p;
else if ( p.x == refPoint.x && p.y < refPoint.y )
refPoint = p;
}
}
bool operator < ( Point a, Point b )
{
if ( a.x == refPoint.x && a.y == refPoint.y )
return 1;
if ( b.x == refPoint.x && b.y == refPoint.y )
return 0;
double r1, r2, ip1, ip2;
r1 = abs ( a.y - refPoint.y ) * 1.0;
ip1 = sqrt( (a.x-refPoint.x)*(a.x-refPoint.x) + (a.y-refPoint.y)*(a.y-refPoint.y) );
r1/=ip1;
r2 = abs ( b.y - refPoint.y ) * 1.0;
ip2 = sqrt( (b.x-refPoint.x)*(b.x-refPoint.x) + (b.y-refPoint.y)*(b.y-refPoint.y) );
r2/=ip2;
if ( a.y > refPoint.y )
r1*=-1;
if ( b.y > refPoint.y )
r2*=-1;
if ( r1 > r2 )
return 1;
if ( r1 < r2 )
return 0;
if ( a.y <= refPoint.y )
return ip1 < ip2;
else
return ip1 > ip2;
}