Pagini recente » Cod sursa (job #1961464) | Cod sursa (job #2308239) | Cod sursa (job #1554340) | Cod sursa (job #2902564) | Cod sursa (job #2303676)
#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];
punct start;
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 stk[MAXN];
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
fin >> n;
start.x = start.y = 1e9;
int inds = 0;
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];
inds = i;
}
}
swap(pct[1], pct[inds]);
sort(pct + 2, pct + n + 1, comp);
int vf = 0;
stk[++vf] = 2;
stk[++vf] = 3;
for(int i = 4; i <= n; ++i){
punct last = pct[stk[vf]], prec = pct[stk[vf - 1]];
cout << prec.x << " " << prec.y << " " << last.x << " " << last.y << " " << pct[i].x << " " << pct[i].y << " --> ";
cout << (last.y - prec.y) / (last.x - prec.x) << " " << (pct[i].y - prec.y) / (pct[i].x - prec.x) << "\n";
while(vf > 1 && (last.y - prec.y) * (pct[i].x - prec.x) > (pct[i].y - prec.y) * (last.x - prec.x)){
vf--;
if(vf > 1){
last = pct[stk[vf]];
prec = pct[stk[vf - 1]];
cout << prec.x << " " << prec.y << " " << last.x << " " << last.y << " " << pct[i].x << " " << pct[i].y << " --> ";
cout << (last.y - prec.y) / (last.x - prec.x) << " " << (pct[i].y - prec.y) / (pct[i].x - prec.x) << "\n";
}
}
cout << "\n\n";
stk[++vf] = i;
}
stk[++vf] = 1;
fout << vf << "\n";
for(int i = 1; i <= vf; ++i)
fout << fixed << setprecision(7) << pct[stk[i]].x << " " << pct[stk[i]].y << "\n";
return 0;
}