Pagini recente » Cod sursa (job #1099867) | Cod sursa (job #1814461) | Cod sursa (job #1535692) | Cod sursa (job #2977246) | Cod sursa (job #1166815)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const double INF = 1000000000;
struct pct{
double x, y;
};
int n, i, k;
pct v[120002], o, sol[120002];
double cross(pct a, pct b, pct c) {
return a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - a.x * c.y - b.x * a.y;
}
bool cmp(pct a, pct b) {
if(cross(o, a, b) > 0) {
return true;
}
return false;
}
int main() {
fin >> n;
o.x = o.y = INF;
for(i = 0; i < n; i++) {
fin >> v[i].x >> v[i].y;
if(v[i].x <= o.x) {
if(v[i].x == o.x) {
if(v[i].y < o.y) {
o.y = v[i].y;
k = i;
}
}else {
o.x = v[i].x;
o.y = v[i].y;
k = i;
}
}
}
swap(v[0], v[k]);
sort(v, v+n, cmp);
sol[0] = v[0];
sol[1] = v[1];
int nr = 1;
for(i = 2; i < n; i++) {
while(cross(v[nr-1], v[nr], v[i]) < 0) {
nr--;
}
nr++;
sol[nr] = v[i];
}
fout << nr + 1 << '\n';
for(i = 0; i <= nr; i++) {
fout << fixed << setprecision(6) << sol[i].x << ' ' << sol[i].y << '\n';
}
fin.close();
fout.close();
return 0;
}