Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #1683856) | Cod sursa (job #2362092)
#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;
int n;
pair <double, double> v[Nmax];
bool used[Nmax];
int st[Nmax], top=2;
double det(int a, int b, int c)
{
double ax=v[a].first, ay=v[a].second;
double bx=v[b].first, by=v[b].second;
double cx=v[c].first, cy=v[c].second;
double ans=0;
ans+=ax*by;
ans+=bx*cy;
ans+=cx*ay;
ans-=cx*by;
ans-=ax*cy;
ans-=bx*ay;
return ans;
}
int main(){
f >> n;
for (int i = 1; i <= n; i++){
double x, y;
f >> x >> y;
v[i]={x, y};
}
sort(v+1, v+n+1);
st[1]=1;
st[2]=2;
used[2]=1;
for (int i = 3; i <= n; i++)
{
if(used[i] == 1) continue;
while(top >= 2 && det(st[top], st[top-1], i) < EPS)
{
used[st[top]]=0;
top--;
}
top++;
used[i]=1;
st[top]=i;
}
for (int i = n-1; i >= 1; i--)
{
if(used[i] == 1) continue;
while(top >= 2 && det(st[top], st[top-1], i) < EPS)
{
used[st[top]]=0;
top--;
}
top++;
st[top]=i;
used[i]=1;
}
top--;
g << top << '\n';
for (int i = top; i >= 1; i--)
g << fixed << setprecision(12) << v[st[i]].first << " " << fixed << setprecision(12) << v[st[i]].second << '\n';
return 0;
}