Pagini recente » Cod sursa (job #3284782) | Cod sursa (job #2056502) | Cod sursa (job #143629) | Cod sursa (job #1453131) | Cod sursa (job #2829932)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point {
long double x, y;
};
point points[10003];
int N, k;
int st[10003];
bool sel[10003];
long long det(point a, point b, point c)
{
// a11 a12 a13
// a21 a22 a23
// a31 a32 a33
return a.x*b.y*1+a.y*1*c.x+1*b.x*c.y-1*b.y*c.x-1*c.y*a.x-1*a.y*b.x;
}
void infasuratoare()
{
st[++k] = 1;
st[++k] = 2;
sel[1] = sel[2] = true;
// prima bucata
for(int i = 3; i <= N; i++)
{
while(k >= 2 && det(points[st[k - 1]], points[st[k]], points[i]) >= 0)
{
sel[st[k]] = 0;
--k;
}
st[++k] = i;
sel[i] = true;
}
for(int i = N; i >= 1; i--)
{
if(sel[i])
continue;
while(k >= 2 && det(points[st[k - 1]], points[st[k]], points[i]) >= 0)
{
sel[st[k]] = 0;
--k;
}
st[++k] = i;
sel[i] = true;
}
}
int main()
{
f >> N;
for(int i = 1; i <= N; i++)
{
f >> points[i].x >> points[i].y;
}
sort(points + 1, points + N + 1, [](point a, point b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
});
infasuratoare();
g << k - 1 << "\n";
for(int i = k - 1; i >= 1; i--)
g << setprecision(6) << fixed << points[st[i]].x << " " << points[st[i]].y << "\n";
return 0;
}