Pagini recente » Cod sursa (job #1518370) | Cod sursa (job #1314579) | Cod sursa (job #1128777) | Cod sursa (job #2131886) | Cod sursa (job #2919000)
#include <fstream>
#include <algorithm>
#include <stack>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n, i, n2, p1[120100], p2[120100], l1, l2;
pair<double, double> coord[120100];
const double eps = 0.000000000001;
double tg1, tg2;
bool ccw(int i1, int i2, int i3)
{
if (abs(coord[i1].first - coord[i2].first) <= eps)
{
if (abs(coord[i3].first - coord[i2].first) <= eps)
return false;
if (coord[i1].second < coord[i2].second + eps) {
if (coord[i3].first < coord[i1].first + eps)
return true;
return false;
}
if (coord[i3].first + eps > coord[i1].first)
return true;
return false;
}
if (abs(coord[i2].first - coord[i3].first) <= eps)
{
if (coord[i2].second < coord[i3].second + eps) {
if (coord[i1].first < coord[i2].first + eps)
return true;
return false;
}
if (coord[i1].first + eps > coord[i2].first)
return true;
return false;
}
tg1 = (coord[i2].second - coord[i1].second);
tg1 = tg1 / (coord[i2].first - coord[i1].first);
tg2 = (coord[i3].second - coord[i1].second);
tg2 = tg2 / (coord[i3].first - coord[i1].first);
if (tg2 + eps > tg1)
return true;
return false;
}
int main()
{
f >> n;
for (i = 1; i <= n; i++)
f >> coord[i].first >> coord[i].second;
sort(coord+1, coord+n+1);
n2 = n;
for (i = 2; i <= n; i++)
{
if (coord[i].first == coord[i-1].first && coord[i].second == coord[i-1].second)
{
coord[i].first = coord[i].second = 1000000001;
n2--;
}
}
sort(coord+1, coord+n+1);
n = n2;
l1 = l2 = 0;
if (n == 1)
g << 1 << '\n' << coord[1].first << ' ' << coord[1].second;
else if (n == 2)
g << 2 << '\n' << coord[1].first << ' ' << coord[1].second << '\n' << coord[2].first << ' ' << coord[2].second;
else
{
for (i = 1; i <= n; i++)
{
while (l1 >= 2 && !ccw(p1[l1-1], p1[l1], i))
p1[l1--] = 0;
p1[++l1] = i;
}
for (i = n; i >= 1; i--)
{
while (l2 >= 2 && !ccw(p2[l2-1], p2[l2], i))
p2[l2--] = 0;
p2[++l2] = i;
}
p1[l1--] = 0;
p2[l2--] = 0;
g << l1+l2 << '\n';
for (i = 1; i <= l1; i++)
g << coord[p1[i]].first << ' ' << coord[p1[i]].second << '\n';
for (i = 1; i <= l2; i++)
g << coord[p2[i]].first << ' ' << coord[p2[i]].second << '\n';
}
f.close();
g.close();
return 0;
}