Pagini recente » Cod sursa (job #2367631) | Cod sursa (job #2741518) | Cod sursa (job #2344392) | Cod sursa (job #166737) | Cod sursa (job #755531)
Cod sursa(job #755531)
#include <fstream>
#include<algorithm>
#include<math.h>
using namespace std;
#define maxn 120000
#define INF 1000000000
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
double X[maxn],Y[maxn];
long double V[maxn];
int pi,IND[maxn],n,ST[maxn];
long double semn(int i1,int i2,int i3);
bool cmpf(int i,int j);
int main()
{
int i;
X[0]=INF;Y[0]=INF;
fin>>n;
pi=0;
for(i=1;i<=n;i++)
{
fin>>X[i]>>Y[i];
if(X[i]<X[pi] || (X[i]==X[pi] && Y[i]<Y[pi])) pi=i;
}
for(i=1;i<=n;i++)
{
if(i==pi) continue;
IND[++IND[0]]=i;
}
sort(IND+1,IND+IND[0]+1,cmpf);
ST[ST[0]=1]=pi;
for(i=1;i<=IND[0];i++)
{
if(IND[i]==pi) continue;
while(ST[0]>=2 && semn(ST[ST[0]-1],ST[ST[0]],IND[i])>0) --ST[0];
ST[++ST[0]] = IND[i];
}
ST[++ST[0]]=pi;
fout<<ST[0]-1<<'\n';
reverse(ST+1,ST+ST[0]+1);
for(int i = 1;i < ST[0]; ++i)
{
fout<<X[ST[i]]<<' '<<Y[ST[i]]<<'\n';
}
return 0;
}
bool cmpf(int i,int j)
{
return (double)(X[i] - X[pi]) * (Y[j] - Y[pi]) < (double)(X[j] - X[pi]) * (Y[i] - Y[pi]);
}
long double semn(int i1,int i2,int i3)
{
return (long double)X[i1]*Y[i2]+X[i2]*Y[i3]+X[i3]*Y[i1]-Y[i1]*X[i2]-Y[i2]*X[i3]-Y[i3]*X[i1];
}