Pagini recente » Cod sursa (job #2983456) | Cod sursa (job #995647) | Cod sursa (job #1663108) | Cod sursa (job #1647217) | Cod sursa (job #1883125)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define NMAX 120005
#define Punct pair<double, double>
#define X first
#define Y second
using namespace std;
Punct S[NMAX];
int n, k = 2;
double x, y;
Punct F;
vector<Punct> V;
double determinant(Punct a, Punct b, Punct c)
{
return (b.X - a.X) * (c.Y - a.Y) - (b.Y - a.Y) * (c.X - a.X);
}
bool compare(Punct a, Punct b)
{
return (determinant(F, a, b) > 0);
}
void read()
{
freopen("infasuratoare.in", "r", stdin);
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%lf %lf", &x, &y);
V.push_back(make_pair(x, y));
}
double minx = 0, miny = 0;
for(int i = 0; i < n; i++)
if(V[i].X < V[minx].X)
minx = i;
miny = minx;
for(int i = 0; i < n; i++)
if(V[i].X == V[minx].X && V[i].Y < V[miny].Y)
miny = i;
Punct aux;
aux = V[0];
V[0] = V[miny];
V[miny] = aux;
F = V[0];
}
void solve()
{
sort(V.begin() + 1, V.end(), compare);
for(int i = 0; i < 2; i++)
S[i] = V[i];
int j = 2;
while(j < n)
{
while(determinant(V[k - 2], V[k - 1], V[j]) < 0 && k > 0)
k--;
V[k] = V[j++];
k++;
}
}
void print()
{
freopen("infasuratoare.out", "w", stdout);
for(int i = 1; i < k; i++)
printf("%lf %lf\n", V[i].X, V[i].Y);
printf("%lf %lf\n", V[0].X, V[0].Y);
}
int main()
{
read();
solve();
print();
//for(int i = 0; i < n; i++)
//cerr << V[i].X << " " << V[i].Y << endl;
return 0;
}