Pagini recente » Cod sursa (job #2876396) | Cod sursa (job #756347) | Cod sursa (job #377809) | Cod sursa (job #2584656) | Cod sursa (job #1866005)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define nMax 120001
#define pdd pair<double, double>
#define x first
#define y second
#define mkp make_pair
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, top;
pdd pct[nMax], stck[nMax];
double cross_product(const pdd &a, const pdd &b, const pdd &c)
{
return a.x*b.y + a.y*c.x + b.x*c.y - c.x*b.y - b.x*a.y - a.x*c.y;
}
int cmp(const pdd &a, const pdd&b)
{
return cross_product(pct[1], a, b)<0;
}
int main()
{
double a, b;
fin>>n;
for(int i=1; i<=n; i++)
{
fin>>a>>b;
pct[i]=mkp(a, b);
}
int poz=1;
for(int i=2; i<=n; i++)
if(pct[i]<pct[poz])
poz=i;
swap(pct[1], pct[poz]);
sort(pct+2, pct+n+1, cmp);
stck[++top]=pct[1];
stck[++top]=pct[2];
for(int i=3; i<=n; i++)
{
while(top>=2 && cross_product(stck[top-1], stck[top], pct[i])>0)
top--;
stck[++top]=pct[i];
}
fout<<top<<'\n';
for(int i=top; i>=1; i--)
fout<<fixed<<setprecision(6)<<stck[i].x<<" "<<stck[i].y<<'\n';
}