Pagini recente » Cod sursa (job #2648955) | Cod sursa (job #2884296) | Cod sursa (job #2548100) | Cod sursa (job #2747073) | Cod sursa (job #2157396)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define N 119999
using namespace std;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
struct plan
{
double x,y;
};
int n, m;
plan bot, v[N], sv[N];
inline double dist ( plan a, plan b )
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
inline int orientation ( plan a, plan b, plan c )
{
int r1,r2;
r1 = (b.x - a.x) * (c.y - b.y);
r2 = (c.x - b.x) * (b.y - a.y);
if ( r1 < r2 )
return -1;
else if ( r1 == r2 )
return 0;
else
return 1;
}
bool cmp ( plan b, plan a )
{
int o;
o = orientation( bot, a, b );
switch (o)
{
case -1 :
return 0;
case 0 :
return dist( bot, a ) > dist( bot, b );
case 1 :
return 1;
}
}
inline void print ( int n );
int main()
{
ios::sync_with_stdio (false);
int i,h;
fin >> n >> bot.x >> bot.y;
--n;
for ( i = 0; i < n; ++i )
{
fin >> v[i].x >> v[i].y;
if ( v[i].x < bot.x )
swap ( bot, v[i] );
else if ( v[i].x == bot.x && v[i].y < bot.y )
swap ( bot, v[i] );
}
sort ( v, v + n, cmp );
//print (n);
/*--n;
for ( i = 0; i < n; ++i )
{
while ( !orientation( bot, v[i], v[i + 1] ) )
++i;
v[m++] = v[i];
}
*/
sv[0] = bot, sv[1] = v[0];
for ( i = h = 1; i < n; ++i )
{
while ( orientation( sv[h - 1], sv[h], v[i] ) == 1 )
--h;
sv[++h] = v[i];
}
fout << h + 1 << '\n';
for ( ; h >= 0; --h )
fout << fixed << setprecision(12) << sv[h].x << " " << sv[h].y << '\n';
}
inline void print ( int n )
{
fout << bot.x << " " << bot.y << '\n';
for ( int i = 0; i < n; ++i )
fout << v[i].x << " " << v[i].y << '\n';
fout << '\n';
}