Pagini recente » Borderou de evaluare (job #1502610) | Borderou de evaluare (job #463440) | Borderou de evaluare (job #1882731) | Cod sursa (job #2602962) | Cod sursa (job #2501009)
#include <bits/stdc++.h>
#define x first
#define y second
#define N_MAX 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, k1, k2, j = 1;
int stiva1[N_MAX], stiva2[N_MAX];
pair < double, double > v[N_MAX];
vector < int > ans;
bool Elim(int *stiva, int k, int pos)
{
pair < double, double > A = v[stiva[k - 1]], B = v[stiva[k]], C = v[pos];
return (((B.x - C.x) * (C.y - A.y) - (B.y - C.y) * (C.x - A.x)) < 0);
}
void ConvexHull(int *stiva, int &k)
{
stiva[++k] = 1;
stiva[++k] = 2;
for (int i = 3; i <= n; i++)
{
while (k > 1 && Elim(stiva, k, i))
k--;
stiva[++k] = i;
}
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1);
ConvexHull(stiva1, k1);
reverse(v + 1, v + n + 1);
ConvexHull(stiva2, k2);
for (int i = 1; ((n - stiva1[i] + 1) != stiva2[1]) && (i <= k1); i++)
{
ans.push_back(n - stiva1[i] + 1);
if (n - stiva1[i] + 1 == stiva2[k2])
k2--;
}
for (int i = j; i <= k2; i++)
ans.push_back(stiva2[i]);
fout << ans.size() << "\n";
for (int i = 0; i < ans.size(); i++)
fout << fixed << setprecision(6) << v[ans[i]].x << " " << v[ans[i]].y << "\n";
return 0;
}