Pagini recente » Cod sursa (job #279839) | Cod sursa (job #2573900) | Cod sursa (job #2050282) | Cod sursa (job #2500414) | Cod sursa (job #1883124)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define cout cerr
#define MAX 120001
using namespace std;
int n,sel,k,l_s;
vector <pair <float, float> > A;
int Q[MAX];
float x,y;
void pus(int val)
{
Q[k++]=val;
if(k>l_s)
l_s=k;
}
float determinant(pair <float, float> a, pair<float, float> b,pair <float, float> c)
{
float xa,ya,xb,yb,xc,yc;
xa=a.first;
ya=a.second;
xb=b.first;
yb=b.second;
xc=c.first;
yc=c.second;
return (xb-xa)*(yc-ya)-(xc-xa)*(yb-ya);
}
bool srt(pair <float, float> a, pair<float, float> b)
{
return (determinant(A[0],a,b) >= 0);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
sel = 0;
for(int i=0; i<n; i++)
{
scanf("%f %f",&x,&y);
A.push_back(make_pair(x,y));
if(x<A[sel].first)
sel=i;
else if(x==A[sel].first)
if(y<A[sel].second)
sel=i;
}
if(sel!=0)
{
pair <float, float> aux;
aux = A[0];
A[0]=A[sel];
A[sel]=aux;
}
sort(A.begin()+1,A.end(),srt);
/*for(int i=0;i<n;i++)
cout<<A[i].first << " "<<A[i].second<<endl;
cout<<endl;*/
pus(0);
for(int i=1;i<n;i++)
if(k==1)
pus(i);
else
{
while(determinant(A[Q[k-2]],A[Q[k-1]],A[i])<0 && k>1)
k--;
pus(i);
}
printf("%d\n",k);
for(int i=0;i<k;i++)
printf("%f %f\n",A[Q[i]].first,A[Q[i]].second);
return 0;
}