Pagini recente » Cod sursa (job #2734755) | Cod sursa (job #1289836) | Cod sursa (job #3247113) | Cod sursa (job #723051) | Cod sursa (job #2416528)
#include <bits/stdc++.h>
using namespace std;
#define punct pair<long double, long double>
#define x first
#define y second
const int MAXN = 120005;
punct pct[MAXN], start;
int ans[MAXN];
bool comp(punct a, punct b){
if(a.x == start.x || b.x == start.x){
if(a.x == b.x)
return a.y > b.y;
return a.x > b.x;
}
double m1 = (start.y - a.y) / (start.x - a.x), m2 = (start.y - b.y) / (start.x - b.x);
return m1 < m2;
}
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, poss = 0;
fin >> n;
start.x = start.y = 1e9;
for(int i = 1; i <= n; ++i){
fin >> pct[i].x >> pct[i].y;
if(pct[i].x < start.x || (pct[i].x == start.x && pct[i].y < start.y)){
start = pct[i];
poss = i;
}
}
swap(pct[1], pct[poss]);
sort(pct + 2, pct + n + 1, comp);
int len = 0;
ans[++len] = 2;
ans[++len] = 3;
for(int i = 4; i <= n; ++i){
punct ult = pct[ans[len]], pen = pct[ans[len - 1]];
while(len > 1 && (ult.y - pen.y) * (pct[i].x - pen.x) > (pct[i].y - pen.y) * (ult.x - pen.x)){
len--;
if(len > 1){
ult = pct[ans[len]];
pen = pct[ans[len - 1]];
}
}
ans[++len] = i;
}
ans[++len] = 1;
fout << len << "\n";
for(int i = 1; i <= len; ++i)
fout << fixed << setprecision(6) << pct[ans[i]].x << " " << pct[ans[i]].y << "\n";
return 0;
}