Pagini recente » Cod sursa (job #1124214) | Cod sursa (job #889246) | Cod sursa (job #972633) | Cod sursa (job #1679189) | Cod sursa (job #1883151)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
struct punct
{
double x,y;
}v[120020],coada[120020];
void citire( )
{
FILE *f=fopen("infasuratoare.in","r");
fscanf(f,"%d",&n);
for(int i=1;i<=n;i++)
{
fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
if(v[i].x<v[1].x)
{
swap(v[i],v[1]);
}
else
if(v[i].x==v[1].x&&v[i].y<v[1].y)
{
swap(v[i],v[1]);
}
}
}
double sbp(punct p1,punct p2, punct p3)
{
double prod= (p2.x - p1.x)*(p3.y-p1.y) - (p3.x-p1.x)*(p2.y-p1.y);
return prod;
}
bool comp(punct p1, punct p2)
{
return (sbp(v[1],p1,p2))>0;
}
void rez( )
{
sort(v+2,v+n+1,comp);
int k=0;
coada[++k]=v[1];
coada[++k]=v[2];
for(int i=3;i<=n;i++)
{
while(k>=2&&sbp(v[k-1],v[k],v[i])<0)
k--;
coada[++k]=v[i];
}
FILE *f1=fopen("infasuratoare.out","w");
fprintf(f1,"%d\n",k);
for(int i=1;i<=k;i++)
fprintf(f1,"%lf %lf\n",coada[i].x,coada[i].y);
}
int main()
{
citire();
rez();
return 0;
}