Pagini recente » Cod sursa (job #1780024) | Cod sursa (job #1676463) | Cod sursa (job #2477161) | Cod sursa (job #1495094) | Cod sursa (job #1950870)
#include <stdio.h>
#include <algorithm>
using namespace std;
FILE*f=fopen("infasuratoare.in","r");
FILE*g=fopen("infasuratoare.out","w");
#define P 1e-12
int use[120002];
struct pct{
double x,y;
int p;
}v[120002],s[120002];
int cmp(pct a, pct b){
return a.y<b.y||((a.y-b.y<=P&&b.y-a.y<=P)&&a.x<b.x);
}
int verif(double x1, double y1, double x2, double y2,int k){
double a,b,c,p=1;
b=1;
if (x1-x2>P) {
a=(y2-y1)/(x1-x2);
c=-a*x1-b*y1;
if (x1>x2) p=-1;
if (a*v[k].x+b*v[k].y+c<=0)
return -p;
return p;
}
else {
if (y1<y2) p=-1;
if (v[k].x-x1<P&&x1-v[k].x<P) return 1;
if (v[k].x>x1) return -p;
else return p;
}
}
int main()
{
int n,i,nr;
fscanf(f,"%d",&n);
for (i=1;i<=n;i++){
fscanf(f,"%lf%lf",&v[i].x,&v[i].y);v[i].p=i;}
sort(v+1,v+n+1,cmp);
s[1]=v[1];use[s[1].p]=1;
s[2]=v[2];use[s[2].p]=1;
nr=2;
for (i=3;i<=n;i++){
while (nr>=2&&verif(s[nr-1].x,s[nr-1].y,s[nr].x,s[nr].y,i)==-1){
use[s[nr].p]=0;
nr--;
}
nr++;
s[nr]=v[i];
use[s[nr].p]=1;
}
for (i=n;i>=1;i--)
if (use[v[i].p]==0||i==1)
{
while (nr>=2&&verif(s[nr-1].x,s[nr-1].y,s[nr].x,s[nr].y,i)==-1){
use[s[nr].p]=0;
nr--;
}
nr++;
s[nr]=v[i];
use[s[nr].p]=1;
}
nr--;
fprintf(g,"%d\n",nr);
for (i=1;i<=nr;i++){
fprintf(g,"%lf %lf\n",s[i].x,s[i].y);
}
fclose(f);
fclose(g);
}