Pagini recente » Cod sursa (job #1080315) | Borderou de evaluare (job #1221567) | Cod sursa (job #479589) | Cod sursa (job #757909) | Cod sursa (job #2209095)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
const double eps = 1e-12;
int pas, poz, st[120001], vf;
bool pus[120001];
struct punct
{
double x, y;
};
punct a[120002];
bool cmp (punct q, punct w)
{
if (q.x > w.x) return false;
if (q.x == w.x && q.y > w.y) return false;
return true;
}
double det (double x1, double y1, double x2, double y2, double x3, double y3)
{
return (x1 * y2 + x2 * y3 + x3 * y1 - y1 * x2 - y2 * x3 - y3 * x1);
}
int n;
int main()
{
f >> n;
for (int i = 1; i <= n; i++)
{
f >> a[i].x >> a[i].y;
}
sort(a+1,a+n+1,cmp);
st[1] = 1;
st[2] = 2;
pus[1] = pus[2] = true;
vf = 2;
poz = 3;
pas = 1;
while (poz > 0)
{
while (pus[poz] == true) {
if (poz == n) pas = -1;
poz = poz + pas;
}
if (poz == 0) break;
while (vf >= 2 && det(a[st[vf-1]].x,a[st[vf-1]].y,a[st[vf]].x,a[st[vf]].y,a[poz].x,a[poz].y) < 0)
{
pus[st[vf]] = false;
vf--;
}
vf++;
st[vf] = poz;
pus[st[vf]] = true;
}
g << vf << '\n';
g << setprecision(6) << fixed;
for (int i = 2; i <= vf; i++)
{
g << a[st[i]].x << " " << a[st[i]].y << '\n';
}
g << a[st[1]].x << " " << a[st[1]].y << '\n';
return 0;
}