Pagini recente » Cod sursa (job #2103061) | Cod sursa (job #2685506) | Cod sursa (job #1137894) | Cod sursa (job #1802640) | Cod sursa (job #293261)
Cod sursa(job #293261)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 121000;
#define eps 1e-9
struct point
{
double x, y;
point(){}
point(double nx, double ny){x = nx; y = ny;}
};
int n;
vector<point> v1, v;
vector<point> S;
point first;
int cmp(point a, point b)
{
return (double)(a.x - first.x) * (b.y - first.y) > (double)(a.y - first.y) * (b.x - first.x);
}
double trig(point a, point b, point c)
{
return (double)(b.x - a.x)*(c.y - a.y) - (double)(b.y - a.y)*(c.x - a.x);
}
void read()
{
scanf("%d", &n);
first.x = 1e9; first.y = 1e9;
for (int i = 1; i <= n; ++i)
{
double x, y;
scanf("%lf%lf", &x, &y);
v1.push_back(point(x,y));
if (x < first.x || (x == first.x && y < first.y))
first = point(x,y);
}
for (int i = 0; i < n; ++i) if (first.x != v1[i].x || first.y != v1[i].y) v.push_back(v1[i]);;
sort(v.begin(), v.end(), cmp);
//for (int i = 0; i < n - 1; ++i) fprintf(stderr,"%lf %lf\n", v[i].x, v[i].y);
}
void print()
{
for (int i = 0; i < S.size(); ++i) fprintf(stderr,"%lf %lf\n", S[i].x, S[i].y);
fprintf(stderr,"\n");
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
read();
S.push_back(first);
for (int i = 0; i < n - 1; ++i)
{
double t = 0;
while(S.size() > 2 && (t = trig(S[S.size()-2],S[S.size()-1],v[i])) < 0)
{
//fprintf(stderr,"%lf-> %lf %lf - %lf %lf\n", t, S[S.size() - 1].x, S[S.size() - 1].y, S[S.size() - 2].x, S[S.size() - 2].y);
S.pop_back();
}
S.push_back(v[i]);
//print();
}
S.push_back(first);
for (int i = 1; i < S.size(); ++i)
printf("%lf %lf\n", S[i].x, S[i].y);
return 0;
}