Pagini recente » Cod sursa (job #185058) | Cod sursa (job #1160987) | Cod sursa (job #1600071) | Cod sursa (job #2566804) | Cod sursa (job #1889377)
#include <cstdio>
#include <algorithm>
#include <iostream>
struct punct
{
double x,y;
};
const int NMAX=120001;
const double INF=1000000001.0,eps=0;
punct v[NMAX],stiva[NMAX];
int marime;
bool cmp(punct a,punct b)
{
return (((a.x-v[1].x)*(b.y-v[1].y))-((b.x-v[1].x)*(a.y-v[1].y)))<eps;
}
double Aria(punct A,punct B,punct C)
{
return (A.x*(B.y-C.y)+B.x*(C.y-A.y)+C.x*(A.y-B.y))/2.0;
}
void infasuratoarea(int n)
{
std::sort(v+1,v+n+1,cmp);
marime=2;
stiva[1]=v[1];
stiva[2]=v[2];
for(int i=3;i<=n;i++)
{
while(marime>=2 && (stiva[marime].x-stiva[marime-1].x)*(v[i].y-stiva[marime-1].y)-(stiva[marime].y-stiva[marime-1].y)*(v[i].x-stiva[marime-1].x)>eps)
marime--;
stiva[++marime]=v[i];
}
}
int main()
{
FILE *in=fopen("infasuratoare.in","r");
int n;
fscanf(in,"%d ",&n);
for(int i=1;i<=n;i++)
{
fscanf(in,"%lf %lf ",&v[i].x,&v[i].y);
if(v[i].y<v[1].y)
std::swap(v[1],v[i]);
else
if(v[i].y==v[1].y)
if(v[i].x<v[1].x)
std::swap(v[1],v[i]);
}
fclose(in);
infasuratoarea(n);
FILE *out=fopen("infasuratoare.out","w");
fprintf(out,"%d\n",marime);
for(int i=marime;i>=1;i--)
{
fprintf(out,"%.8f %.8f\n",stiva[i].x,stiva[i].y);
}
fclose(out);
return 0;
}