Pagini recente » Cod sursa (job #69646) | Cod sursa (job #133975) | Cod sursa (job #49123) | Cod sursa (job #2795832) | Cod sursa (job #268835)
Cod sursa(job #268835)
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#define nmax 120010
using namespace std;
FILE *f=fopen("infasuratoare.in","r"), *g=fopen("infasuratoare.out","w");
struct punct { double x,y;} a[nmax],pst;
int n,i;
inline int isleft(punct p1, punct p2, punct p3)
{
double left=((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y));
if(left<0) return -1;
if(left==0) return 0;
if(left>0) return 1;
}
/*inline int cmp(punct *p1, punct *p2)
{
int left=isleft(pst, *p1,*p2);
if(left==1) return -1;
if(left==-1) return 1;
return 0;
} */
struct cmp{
bool operator()(const punct &a, const punct &b)const
{
int left=isleft(pst, a, b);
if(left==1) return 1;
return 0;
}
};
int main()
{
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%lf %lf",&a[i].x, &a[i].y);
pst=a[1];
int poz=1;
for(i=2;i<=n;i++)
if(a[i].y<pst.y) pst=a[i],poz=i;
else
if(a[i].y==pst.y)
if(a[i].x<pst.x) pst=a[i],poz=i;
punct aux;
aux=a[1];
a[1]=a[poz];
a[poz]=aux;
//qsort(a+2,n-1,sizeof(punct), (int (*)(const void *, const void *))cmp);
sort(a+2,a+n+1,cmp());
punct stiva[nmax];
int k=0;
stiva[++k]=a[1];
stiva[++k]=a[2];
stiva[++k]=a[3];
for(i=4;i<=n;i++)
{
while(isleft(stiva[k-1],stiva[k],a[i])==-1) k--;
stiva[++k]=a[i];
}
fprintf(g,"%d\n",k);
for(i=1;i<=k;i++) fprintf(g,"%.6lf %.6lf\n",stiva[i].x,stiva[i].y);
fclose(f);
fclose(g);
return 0;
}