Pagini recente » Cod sursa (job #1352283) | Cod sursa (job #3032828) | Cod sursa (job #228329) | Cod sursa (job #2846524) | Cod sursa (job #1503196)
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 120010;
int N, Top, HSZ;
pair<double, double> P[NMAX], Stack[NMAX], Hull[NMAX];
double Det(pair<double, double> P1, pair<double, double> P2, pair<double, double> P3)
{
return P1.first * (P2.second - P3.second) + P2.first * (P3.second - P1.second) + P3.first * (P1.second - P2.second);
}
void AddPoints()
{
Top = 0;
Stack[Top ++] = P[1];
Stack[Top ++] = P[2];
for(int i = 3; i <= N; ++ i)
{
while(Top >= 2 && Det(Stack[Top - 2], Stack[Top - 1], P[i]) < 0) Top --;
Stack[Top ++] = P[i];
}
for(int i = 0; i < Top - 1; ++ i) Hull[++ HSZ] = Stack[i];
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%i", &N);
for(int i = 1; i <= N; ++ i) scanf("%lf %lf", &P[i].first, &P[i].second);
sort(P + 1, P + N + 1);
AddPoints();
reverse(P + 1, P + N + 1);
AddPoints();
printf("%i\n", HSZ);
for(int i = 1; i <= HSZ; ++ i) printf("%.10f %.10f\n", Hull[i].first, Hull[i].second);
}