Pagini recente » Cod sursa (job #17988) | Cod sursa (job #1025515) | Cod sursa (job #1486506) | Cod sursa (job #1858862) | Cod sursa (job #1690199)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const int nmax = 12e4;
struct point {double x, y;} p[nmax];
inline double sarrus(point a, point b, point c) {
return a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x;
}
inline bool cmp(point a, point b) {
return sarrus(p[1], a, b) > 0;
}
int main()
{
ios_base::sync_with_stdio(false);
int n, i, poz=1, st[nmax], top=0;
fin >> n;
for(i=1; i<=n; i++) {
fin >> p[i].x >> p[i].y;
if(p[i].x < p[poz].x) poz=i;
if(p[i].x==p[poz].x && p[i].y < p[poz].y) poz=i;
}
swap(p[1], p[poz]);
sort(p+2, p+n+1, cmp);
st[++top]=1;
p[n+1]=p[1];
for(i=2; i<=n; i++) {
st[++top]=i;
while(top && sarrus(p[st[top-1]], p[st[top]], p[i+1]) < 0) top--;
}
fout << top << "\n";
for(i=1; i<=top; i++)
fout << fixed << setprecision(6) << p[st[i]].x << " " << p[st[i]].y << "\n";
fin.close();
fout.close();
return 0;
}