Pagini recente » Cod sursa (job #717479) | Cod sursa (job #652708) | Cod sursa (job #2937309) | Cod sursa (job #2539483) | Cod sursa (job #2442573)
#include <bits/stdc++.h>
#define maxN 120002
#define ld double
#define x first
#define y second
#define Point pair < ld, ld >
#define Sit set<Point>::iterator
using namespace std;
FILE *fin = freopen("infasuratoare.in", "r", stdin);
FILE *fout = freopen("infasuratoare.out", "w", stdout);
int n;
ld CrossProd(Point A, Point B, Point C)
{
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
struct DynCHull
{
set < Point > Up, Dw;
bool bad(Sit it, set < Point > &s)
{
if (s.size() <= 2) return false;
if (it == s.begin()) return false;
if (++ it == s.end()) return false;
auto C = it, B = -- it, A = -- it;
return (CrossProd(*A, *B, *C) < 0);
}
void check_prv(Sit it, set < Point > &s)
{
-- it;
if (s.begin() == it) return ;
while (bad(it, s))
{
auto tmp = it;
++ it;
s.erase(tmp);
}
}
void check_nxt(Sit it, set < Point > &s)
{
if (++ it == s.end()) return ;
while (bad(it, s))
{
auto tmp = it;
++ it;
s.erase(tmp);
}
}
void Insert(Point p, set <Point> &s)
{
auto it = s.insert(p).first;
if (s.size() <= 2) return ;
if (bad(it, s))
{
s.erase(it);
return ;
}
check_prv(it, s);
check_nxt(it, s);
}
void AddPoint(Point p)
{
Insert(p, Up);
Insert({-p.x, -p.y}, Dw);
}
} Ch;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++ i)
{
Point p;
scanf("%lf %lf", &p.x, &p.y);
Ch.AddPoint(p);
}
auto it = Ch.Up.end();
-- it;
Ch.Up.erase(it);
it = Ch.Dw.end();
-- it;
Ch.Dw.erase(it);
for (auto it = Ch.Up.begin(); it != Ch.Up.end(); ++ it)
printf("%.9lf %.9lf\n", it->x, it->y);
for (auto it = Ch.Dw.begin(); it != Ch.Dw.end(); ++ it)
printf("%.9lf %.9lf\n", -it->x, -it->y);
return 0;
}