Pagini recente » Cod sursa (job #1362162) | Cod sursa (job #3190780) | Cod sursa (job #834052) | Cod sursa (job #690731) | Cod sursa (job #1623683)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
using namespace std ;
typedef pair <double, double> Pair ;
const int NMAX = 120005 ;
Pair V[NMAX], S[NMAX], MIN(1000000000, 1000000000) ;
int head, N ;
ifstream fin("infasuratoare.in") ;
ofstream fout("infasuratoare.out") ;
inline double cross_product(Pair O, Pair A, Pair B)
{
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x) ;
}
inline double cmp(Pair A, Pair B)
{
return (A.x - MIN.x) * (B.y - MIN.y) > (B.x - MIN.x) * (A.y - MIN.y) ;
}
int main()
{
int pos ;
fin >> N ;
for(int i = 1 ; i <= N ; ++ i)
{
Pair XY ;
fin >> XY.x >> XY.y ;
if(XY < MIN)
MIN = XY, pos = i ;
V[i] = XY ;
}
swap(V[1], V[pos]) ;
sort(V + 2, V + N + 1, cmp) ;
S[1] = V[1] ;
S[2] = V[2] ;
head = 2 ;
for(int i = 3 ; i <= N ; ++ i)
{
while(head >= 2 && cross_product(V[head - 1], V[head], V[i]) < 0)
-- head ;
S[++head] = V[i] ;
}
fout << head << '\n' ;
fout << fixed << setprecision(9) ;
swap(S[1], S[head + 1]) ;
for(int i = 2 ; i <= head + 1; fout << S[i].x << ' ' << S[i].y << '\n', i ++)
fin.close() ;
fout.close() ;
return 0 ;
}