Pagini recente » Cod sursa (job #1433132) | Cod sursa (job #374703) | Cod sursa (job #667114) | Cod sursa (job #2317641) | Cod sursa (job #2918007)
#include <bits/stdc++.h>
#define last(x) (x.back())
#define penlast(x) (x[x.size()-2])
#define INF 1e9+1
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const int nMAX = 120e3;
typedef long double ld;
int n;
vector<int> stiv;
struct punct {
ld x, y, pan;
bool operator<(const punct&B)const
{
if (pan < 0 && B.pan >= 0)
return false;
if (pan >= 0 && B.pan < 0)
return true;
if (pan != B.pan)
return pan < B.pan;
if (pan == 0)
return x < B.x;
if (pan == INF)
return y < B.y;
return y < B.y;
}
} pct[nMAX + 1];
ld panta(int i, int j)
{
if (pct[i].x == pct[j].x)
return INF;
else
return (pct[j].y-pct[i].y) / (pct[j].x-pct[i].x);
}
int main()
{
fin >> n;
int min = 0;
pct[0] = {INF, INF};
for (int i = 1; i <= n; ++i)
{
fin >> pct[i].x >> pct[i].y;
if (pct[i].y < pct[min].y)
min = i;
else if (pct[i].y == pct[min].y && pct[i].x < pct[min].x)
min = i;
}
swap(pct[1], pct[min]);
for (int i = 2; i <= n; ++i)
pct[i].pan = panta(1, i);
sort(pct + 2, pct + n+1);
stiv.push_back(1);
stiv.push_back(2);
for (int i = 3; i <= n+1; ++i)
{
punct a = pct[penlast(stiv)];
punct b = pct[last(stiv)];
while ((pct[(i-1)%n+1].y-a.y) * (b.x-a.x) <= (b.y-a.y) * (pct[(i-1)%n+1].x-a.x))
{
stiv.pop_back();
a = pct[penlast(stiv)];
b = pct[last(stiv)];
}
stiv.push_back(i);
}
stiv.pop_back();
fout << setprecision(20) << stiv.size() << '\n';
for (int g : stiv)
fout << pct[g].x << ' ' << pct[g].y << '\n';
}