Pagini recente » Cod sursa (job #2694578) | Cod sursa (job #1131217) | Cod sursa (job #1709697) | Cod sursa (job #98386) | Cod sursa (job #1131220)
#include <fstream>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<double,double> C;
C coord[120001];
int punct[120001];
bool viz[120001];
bool u(int a, int o, int b)
{
if ((coord[a].x-coord[o].x) *(coord[b].y-coord[o].y) - (coord[b].x-coord[o].x) * (coord[a].y-coord[o].y) <= 0) return false;
if((coord[a].x-coord[o].x) *(coord[b].y-coord[o].y) - (coord[b].x-coord[o].x) * (coord[a].y-coord[o].y) >=0) return true;
}
int main()
{
ifstream mama("infasuratoare.in");
ofstream tata("infasuratoare.out");
int n,i,j,k;
mama>>n;
for(i=1;i<=n;i++)
mama>>coord[i].x>>coord[i].y;
sort(coord+1,coord+n+1);
punct[1]=1; punct[2]=2;
i=2;
viz[1]=true;
for(j=i+1;j<=n;j++)
{
k=j;
while(k<=n and u(punct[i],punct[i-1],k)==false)
k++;
if(k==n+1) {punct[++i]=j; viz[punct[i-1]]=true;}
else punct[i]=j;
}
viz[n]=true;
punct[++i]=n-1;
for(j=n-2;j>1;j--)
{
if(!viz[j])
{ k=j;
while(k>=1 and u(k,punct[i-1],punct[i])==true)
k--;
if(k==0) punct[++i]=j;
else
punct[i]=j;
}
}
tata<<i<<'\n';
for(j=i;j>=1;j--)
tata<<coord[j].x<<" "<<coord[j].y<<'\n';
return 0;
}