Pagini recente » Cod sursa (job #3195782) | Cod sursa (job #1959237) | Cod sursa (job #3212641) | Cod sursa (job #1446901) | Cod sursa (job #2209521)
#include <cstdio>
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
int const NM = 12e4 + 7;
int n;
int vl [NM] , vr [NM];
typedef long long ll;
struct code
{
double x , y;
int type;
/// 1 stanga
/// -1 dreapta
/// 0 centru
};
code v [NM];
inline bool crt (code a , code b)
{
if(a . x == b . x)
return a . y < b . y;
return a . x < b . x;
}
inline int where (code a , code b , code p)
{
return ((a.x*b.y+b.x*p.y+p.x*a.y)-(b.y*p.x+p.y*a.x+a.y*b.x));
}
int szl , szr;
inline void left ()
{
int i;
vl [++ szl] = 1;
for(i = 2 ; i <= n ; ++ i)
{
while( szl > 1 && where (v [vl [szl - 1]] , v [vl [szl]] , v [i]) > 0)
-- szl;
vl [++ szl] = i;
}
return;
}
inline void right ()
{
int i = 2;
vr [++ szr] = 1;
for(i = 2 ; i <= n ; ++ i)
{
while(szr > 1 && where (v [vr [szr - 1]] , v [vr [szr]] , v [i]) < 0)
-- szr;
vr [++ szr] = i;
}
return ;
}
char const in [] = "infasuratoare.in";
char const out [] = "infasuratoare.out";
ofstream cout (out);
int main ()
{
int i;
FILE *cin ;
cin = fopen (in , "r");
fscanf (cin , "%d" , &n);
for(i = 1 ; i <= n ; ++ i)
fscanf (cin , "%lf %lf" , &v [i] . x , &v [i] . y);
sort (v + 1 , v + n + 1 , crt);
code start = v [1] , finish = v [n];
for(i = 2 ; i < n ; ++ i)
v [i] . type = where (start , finish , v [i]);
left ();
right ();
cout << szl + szr - 2 << '\n';
for(i = 1 ; i <= szr ; ++ i)
cout << fixed << setprecision(12) << v [vr [i]] . x << ' ' << v [vr [i]] . y << '\n';
// cout << '\n';
for(i = szl - 1 ; i > 1 ; -- i)
cout << fixed << setprecision(12) << v [vl [i]] . x << ' ' << v [vl [i]] . y << '\n';
return 0;
}