Pagini recente » Cod sursa (job #1221104) | Cod sursa (job #2050956) | Cod sursa (job #2477004) | Cod sursa (job #2572820) | Cod sursa (job #2294330)
#include <cstdio>
#include <algorithm>
#define DIM 120001
using namespace std;
struct punct{
double x,y;
};
punct v[DIM],s[DIM];
double arie (punct a,punct b,punct c){
return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
int cmp (punct a,punct b){
punct c;
c.x=0;
c.y=0;
if (arie (c,a,b)!=0)
return arie (c,a,b)>0;
return a.x*a.x+a.y*a.y > b.x*b.x+b.y*b.y;
}
int main()
{
FILE *fin=fopen ("infasuratoare.in","r");
FILE *fout=fopen ("infasuratoare.out","w");
int n,i,j,mini,elem;
fscanf (fin,"%d",&n);
mini=0;
v[0].x=1.0*1000000000;
v[0].y=1.0*1000000000;
for (i=1;i<=n;i++){
fscanf (fin,"%lf%lf",&v[i].x,&v[i].y);
if (v[i].y<v[mini].y || (v[i].y==v[mini].y && v[i].x<v[mini].x))
mini=i;
}
v[0]=v[mini];
v[mini]=v[1];
v[1]=v[0];
for (i=1;i<=n;i++){
v[i].x-=v[0].x;
v[i].y-=v[0].y;
}
sort (v+2,v+n+1,cmp);
for (j=3;j<=n;j++){
if (arie (v[j],v[1],v[2]))
break;
}
i=2;
j--;
while (i<j){
swap(v[i],v[j]);
i++;
j--;
}
s[1]=v[1];
s[2]=v[2];
elem=2;
for (j=3;j<=n;j++){
while (elem>=2 && arie (s[elem-1],s[elem],v[j])<0) // nu il pot adauga aici pe v[j]
elem--;
s[++elem]=v[j];
}
fprintf (fout,"%d\n",elem);
for (i=1;i<=elem;i++)
fprintf (fout,"%lf %lf\n",s[i].x+v[0].x,s[i].y+v[0].y);
return 0;
}