Pagini recente » Borderou de evaluare (job #3001095) | Cod sursa (job #793970) | Cod sursa (job #1130269) | Cod sursa (job #2054194)
#include <bits/stdc++.h>
#define dbg(x) cerr<<#x": "<<x<<"\n"
using namespace std;
//ifstream fin("infasuratoare.in");
//ofstream fout("infasuratoare.out");
int n,i,m;
struct p{ double x, y;} puncte[120001],top[120001];
double area(p a, p b,p c)
{
return a.x*b.y + b.x*c.y + a.y*c.x - c.x*b.y - b.x*a.y - c.y*a.x;
}
bool comparator(p a, p b)
{
return area(puncte[1], a, b)>=0;
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
m=1;
scanf("%d", &n);
for (i=1;i<=n;i++)
{
//cin>>puncte[i].x>>puncte[i].y;
scanf("%lf%lf", &puncte[i].x, &puncte[i].y);
if (puncte[m].x<puncte[i].x)
m=i;
else if (puncte[i].x == puncte[m].x && puncte[i].y < puncte[m].y)
m=i;
}
//puncte[0] = {0., 0.};
swap(puncte[1],puncte[m]);
sort(puncte+2, puncte+n+1, comparator);
int x=0;
for (i=1;i<=n;i++)
{
while (x>1&&area(top[x-1],top[x],puncte[i])<0)
{
//dbg(area(top[x-1],top[x],puncte[i]));
//dbg(top[x].x);
//dbg(top[x].y);
//dbg(i);
x--;
}
top[++x]=puncte[i];
}
printf("%d\n", x);
for (int i=1;i<=x;i++)
//cout<<fixed<<top[i].x<<' '<<top[i].y<<'\n';
printf("%.6lf %.6lf\n", top[i].x, top[i].y);
return 0;
}