Pagini recente » Cod sursa (job #2366784) | Cod sursa (job #3148895) | Cod sursa (job #3181031) | Cod sursa (job #232919) | Cod sursa (job #1650634)
#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 - c.x*b.y - c.y*a.x - b.x*a.y;
}
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);
p[n+1]=p[1];
st[++top]=1;
for(i=2; i<=n; i++)
{
st[++top]=i;
while(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";
return 0;
}