Pagini recente » Cod sursa (job #2571885) | Cod sursa (job #3247798) | Cod sursa (job #1329166) | Cod sursa (job #3176324) | Cod sursa (job #1920874)
#include <bits/stdc++.h>
#define x first
#define y second
#define PII pair<double, double>
using namespace std;
int n, cnt;
PII p[125000];
PII S[125000];
double check(PII a, PII b, PII c)
{
return 1.0 * ((b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y));
}
bool cmp(PII a, PII b)
{
return (check(p[1], a, b) < 0);
}
int main(){
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin >> n;
for (int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y;
sort(p+1, p+n+1);
sort(p+2, p+n+1, cmp);
S[1] = p[1];
S[2] = p[2];
cnt = 2;
for (int i = 3; i <= n; i++)
{
while (cnt >= 2 && check(S[cnt - 1], S[cnt], p[i]) > 0) --cnt;
S[++cnt] = p[i];
}
cout << cnt << "\n";
cout << setprecision(6) << fixed;
for (; cnt; cnt--)
cout << S[cnt].x << " " << S[cnt].y << "\n";
cerr << "Fucking time elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
return 0;
}