Pagini recente » Cod sursa (job #1117172) | Cod sursa (job #2786686) | Cod sursa (job #576286) | Cod sursa (job #77577) | Cod sursa (job #450902)
Cod sursa(job #450902)
#include<cmath>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<stack>
using namespace std;
#define elif else if
const double eps = 0.0000000000001;
struct point
{
double x, y;
};
int n, pmin;
point p[120001];
double minx = 120001, miny = 120001;
int st[120001], nr = -1;
void read();
void write();
void scan();
double angle( point a )
{
double xi, yi;
xi = a.x - minx;
yi = a.y - miny;
if ( fabs( xi ) < eps )
return 90;
if ( xi > 0 )
return 180 * ( atan( yi / xi ) / M_PI );
else
return 180 - fabs( 180 * ( atan( yi / xi ) / M_PI ) );
}
double dist_2( point a )
{
double xi, yi;
xi = a.x - minx;
yi = a.y - miny;
return xi * xi + yi * yi;
}
bool cond( const point& a, const point b )
{
if ( fabs( angle( a ) - angle( b ) ) > eps )
return angle( a ) < angle( b );
return dist_2( a ) - dist_2( b ) > eps;
}
bool change( point x )
{
//imi iau ultimele doua din stack
point top = p[st[nr]];
point pen = p[st[nr - 1]];
//----
/*double x1, y1, x2, y2;
x1 = top.x - pen.x;
y1 = top.y - pen.y;
x2 = x.x - pen.x;
y2 = x.y - pen.y;
if( x1 * y2 - x2 * y1 <= 0 )*/
if( ( top.x - pen.x ) * ( x.y - pen.y ) - ( x.x - pen.x ) * ( top.y - pen.y ) <= 0 )
return 1;
return 0;
}
int main()
{
read();
scan();
write();
return 0;
}
void read()
{
ifstream fin( "infasuratoare.in" );
fin >> n;
for ( int i = 0; i < n; ++i )
{
fin >> p[i].x >> p[i].y;
if ( p[i].y < miny )
{
pmin = i;
minx = p[i].x;
miny = p[i].y;
}
elif ( ( p[i].y - miny < eps ) && p[i].x < minx )
{
pmin = i;
minx = p[i].x;
}
}
point aux = p[pmin];
p[pmin] = p[0];
p[0] = aux;
fin.close();
}
void write()
{
ofstream fout( "infasuratoare.out" );
fout << nr + 1 << '\n';
for ( int i = 0; i <= nr; ++i )
fout /*<< fixed << setprecision(10)*/ << p[st[i]].x << ' ' << p[st[i]].y << '\n';
fout.close();
}
void scan()
{
sort( p + 1, p + n, cond );
st[++nr] = 0;
st[++nr] = 1;
st[++nr] = 2;
for ( int i = 3; i < n; ++i ) // O(n * not_ok )
{
while ( change( p[i] ) )
{
--nr;
if ( nr == 0 )
break;
}
st[++nr] = i;
}
}