Pagini recente » Cod sursa (job #2316611) | Cod sursa (job #3128917) | Cod sursa (job #1485070) | Cod sursa (job #1068004) | Cod sursa (job #2128958)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct{double x,y;} p[120006],s[120006];
int n,i,nrs=2;
double detr(punct a,punct b,punct c)
{
return a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-c.x*b.y-b.x*a.y;
}
bool comp(punct a,punct b)
{
if(detr(p[0],a,b)>0) return true;
return false;
}
int main()
{
fin>>n;
fin>>p[0].x>>p[0].y;
for(i=1;i<=n-1;i++)
{
fin>>p[i].x>>p[i].y;
if(p[0].x>p[i].x||(p[0].x==p[i].x&&p[0].y>p[i].y)) swap(p[0],p[i]);
}
sort(p+1,p+n,comp);
s[1]=p[0];
s[2]=p[1];
for(i=2;i<n;i++)
{
while(detr(s[nrs-1],s[nrs],p[i])<0&&nrs>=2)
nrs--;
s[++nrs]=p[i];
}
fout<<nrs<<'\n';
for(i=1;i<=nrs;i++)
fout<<s[i].x<<" "<<s[i].y<<'\n';
return 0;
}