Pagini recente » Cod sursa (job #590925) | Cod sursa (job #68091) | Cod sursa (job #1750418) | Cod sursa (job #1650997) | Cod sursa (job #2363987)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define nmax 120000
#define pdd pair<double,double>
#define x first
#define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,mn;
pdd v[nmax+5],s[nmax+5];
int det(pdd A,pdd B, pdd C)
{
return A.x*B.y + B.x*C.y + C.x*A.y-C.y*A.x-B.y*C.x-A.y*B.x;
}
bool comp(pdd A, pdd B)
{
return det(A,B,v[1])>=0;
}
int main()
{
fin>>n;
v[0] = {1e9+1,0};
for(int i=1;i<=n;i++)
{
fin>>v[i].x>>v[i].y;
if(v[i].x<v[mn].x || v[i].x==v[mn].x && v[i].y<v[mn].y)
mn=i;
}
swap(v[mn],v[1]);
sort(v+2,v+1+n,comp);
int last=2;
s[1]=v[1],s[2]=v[2];
for(int i=3;i<=n;i++)
{
while(last>=2 && det(s[last-1],s[last],v[i])<0)last--;
s[++last]=v[i];
}
fout<<last<<"\n";
fout<<fixed<<setprecision(12);
for(int i=1;i<=last;i++)
fout<<s[i].x<<" "<<s[i].y<<"\n";
return 0;
}