Pagini recente » Cod sursa (job #2225571) | Cod sursa (job #751105) | Cod sursa (job #855673) | Cod sursa (job #1073732) | Cod sursa (job #1404557)
#include<bits/stdc++.h>
#define Nmax 120001
#define X first
#define Y second
#define Punct pair < double , double >
using namespace std;
Punct Point[Nmax], Stiva[Nmax];
int N, H;
double product(Punct A, Punct B, Punct C)
{
return A.X * (B.Y - C.Y) + B.X * (C.Y - A.Y) + C.X * (A.Y - B.Y);
}
bool cmp(Punct A, Punct B)
{
return product(Point[1], A, B) < 0;
}
void Read()
{
freopen("infasuratoare.in", "r", stdin);
scanf("%d", &N);
for(int i = 1; i <= N; ++ i) {
scanf("%lf %lf", &Point[i].X, &Point[i].Y);
if(Point[i] < Point[1])
swap(Point[i], Point[1]);
}
}
void Write()
{
freopen("infasuratoare.out", "w", stdout);
printf("%d", H);
for(int i = H; i; -- i)
printf("\n%lf %lf", Stiva[i]);
}
void Infasuratoare()
{
sort(Point + 2, Point + 1 + N, cmp);
Stiva[1] = Point[1];
Stiva[(H = 2)] = Point[2];
for(int i = 3; i <= N; Stiva[++ H] = Point[i], ++ i)
while(H >= 2 && product(Stiva[H - 1], Stiva[H], Point[i]) > 0)
-- H;
Write();
}
int main()
{
Read();
Infasuratoare();
return 0;
}