Pagini recente » Cod sursa (job #3230037) | Cod sursa (job #683965) | Cod sursa (job #2965779) | Cod sursa (job #98303) | Cod sursa (job #2314273)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define Nmax 120005
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const double EPS=1e-12;
struct point{
double x, y;
}a[Nmax];
double x, y;
int n, st[Nmax];
bool seen[Nmax];
bool cmp(point a, point b)
{
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
void print()
{
for (int i = 1; i <= n; i++)
cout << fixed << setprecision(2) << double(a[i].x) << " " << fixed << setprecision(2) << double(a[i].y) << '\n';
cout << '\n';
}
double determinant(point a, point b, point c)
{
return a.x*b.y + b.x*c.y + a.y*c.x - b.y*c.x - c.y*a.x - b.x*a.y;
}
int main()
{
f >> n;
for (int i = 1; i <= n; i++)
{
f >> x >> y;
a[i]={x, y};
}
sort(a+1, a+n+1, cmp);
//print();
st[1]=1, st[2]=2;
seen[2]=1;
int i=2, top=2;
for (int i = 3; i <= n; i++)
{
if(seen[i] == 1) continue;
while(top>=2 && determinant(a[st[top]], a[st[top-1]], a[i])<EPS)
{
seen[st[top]]=0;
top--;
}
st[++top]=i;
seen[i]=1;
}
for (int i = n-1; i >= 1; i--)
{
if(seen[i] == 1) continue;
while(top>=2 && determinant(a[st[top]], a[st[top-1]], a[i])<EPS)
{
seen[st[top]]=0;
top--;
}
st[++top]=i;
seen[i]=1;
}
g << top-1<< '\n';
for (int i = top-1; i > 0; i--) g << fixed << setprecision(6) << a[st[i]].x << " " << fixed << setprecision(6) << a[st[i]].y << '\n';
return 0;
}