Pagini recente » Cod sursa (job #2788464) | Cod sursa (job #461556) | Clasament marcel1 | Cod sursa (job #2019165) | Cod sursa (job #2557776)
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <cstring>
#include <iomanip>
#define pii pair <double, double>
#define fs first
#define sc second
#define Nmax 120005
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
pii a[Nmax];
int st[Nmax], top;
bool used[Nmax];
int det(int x, int y, int z)
{
int x1=a[x].fs, y1=a[x].sc;
int x2=a[y].fs, y2=a[y].sc;
int x3=a[z].fs, y3=a[z].sc;
int ans=0;
ans+=x1*y2+y1*x3+x2*y3;
ans-=x3*y2+y3*x1+y1*x2;
return ans;
}
int main()
{
f >> n;
for (int i = 1; i <= n; i++) f >> a[i].fs >> a[i].sc;
sort (a+1, a+n+1);
//for (int i = 1; i <= n; i++)
//cout << a[i].fs << " " << a[i].sc << '\n';
//cout << '\n';
st[1]=1, st[2]=2;
used[1]=used[2]=1;
top=2;
for (int i = 3; i <= n; i++)
{
while (top > 1 && det(st[top], st[top-1], i) > 0)
{
used[st[top]]=0;
top--;
}
top++;
st[top]=i;
used[st[top]]=1;
}
for (int i = n-1; i >= 1;i--)
{
if (used[i] == 1) continue;
while (top > 1 && det(st[top], st[top-1], i) > 0)
{
used[st[top]]=0;
top--;
}
top++;
st[top]=i;
used[st[top]]=1;
}
g << top << '\n';
for (int i = top; i >= 1; i--)
g << fixed << setprecision(12) << a[st[i]].fs << " " << fixed << setprecision(12) << a[st[i]].sc << '\n';
return 0;
}