Pagini recente » Cod sursa (job #26863) | Cod sursa (job #142727) | Cod sursa (job #2525038) | Cod sursa (job #2950033) | Cod sursa (job #2364167)
#include <bits/stdc++.h>
#define nmax 120000
#define pdd pair<double,double>
#define x first
#define y second
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n, mn;
pdd v[nmax + 5], s[nmax + 5];
double det(pdd A, pdd B, pdd C)
{
return A.x * B.y + B.x * C.y + C.x * A.y - C.y * A.x - B.y * C.x - A.y * B.x;
}
bool comp(pdd A, pdd B)
{
return det(A, B, v[1]) >= 0;
}
int main()
{
in >> n;
v[0] = {1e9+1, 0};
for (int i = 1; i <= n; ++i)
{
in >> v[i].x >> v[i].y;
if (v[i].x < v[mn].x || v[i].x == v[mn].x && v[i].y < v[mn].y)
mn = i;
}
swap(v[mn], v[1]);
sort(v + 2, v + 1 + n, comp);
int last = 2;
s[1] = v[1];
s[2] = v[2];
for (int i = 3; i <= n; ++i)
{
while (last >= 2 && det(s[last - 1], s[last], v[i]) < 0)
--last;
s[++last] = v[i];
}
out << last << '\n';
out << fixed << setprecision(12);
for (int i = 1; i <= last; ++i)
out << s[i].x << " " << s[i].y << '\n';
return 0;
}