Pagini recente » Cod sursa (job #1418396) | Cod sursa (job #2191982) | Cod sursa (job #327247) | Cod sursa (job #332098) | Cod sursa (job #2300196)
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct punct
{
double x;
double y;
};
double intoarcere (punct A, punct B, punct C)
{
return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}
bool cmp (punct A, punct B)
{
if (A.y == B.y) return A.x < B.x;
return A.y < B.y;
}
int main()
{
int n, nr = 0;
in.sync_with_stdio(false);
in >> n;
vector<punct> v;
vector<int> Q(n + 1);
vector<bool> OK(n + 1);
for (int i = 1; i <= n; i++)
{
double x, y;
in >> x >> y;
v.push_back({x, y});
}
sort(v.begin(), v.end(), cmp);
Q[++nr] = 0;
Q[++nr] = 1;
OK[1] = 1;
for (int i = 2; i < n; i++)
{
while (nr > 1 && intoarcere(v[Q[nr - 1]], v[Q[nr]], v[i]) <= 0)
{
OK[Q[nr]] = 0;
nr--;
}
Q[++nr] = i;
OK[i] = 1;
}
const int lim = nr;
for (int i = n - 2; i >= 0; i--)
{
if (OK[i]) continue;
while (nr > lim && intoarcere(v[Q[nr - 1]], v[Q[nr]], v[i]) <= 0)
{
OK[Q[nr]] = 0;
nr--;
}
Q[++nr] = i;
OK[i] = 1;
}
out << nr - 1 << '\n';
for (int i = 1; i < nr; i++)
out << fixed << setprecision(12) << v[Q[i]].x << ' ' << v[Q[i]].y << '\n';
return 0;
}