Pagini recente » Cod sursa (job #2200591) | Cod sursa (job #2780796) | Cod sursa (job #2841803) | Cod sursa (job #2812270) | Cod sursa (job #2917925)
#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;
return pan < B.pan;
}
} 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)];
if ((b.y-a.y) * pct[i].x - (b.x - a.x) * pct[i].y + a.y*b.x - b.y*a.x > 0)
stiv.pop_back();
stiv.push_back(i);
}
stiv.pop_back();
fout << stiv.size() << '\n';
for (int g : stiv)
fout << pct[g].x << ' ' << pct[g].y << '\n';
}