Pagini recente » Borderou de evaluare (job #2029171) | Cod sursa (job #806187) | Cod sursa (job #511561) | Borderou de evaluare (job #1331034) | Cod sursa (job #915497)
Cod sursa(job #915497)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
struct pct
{
int poz;
double x,y;
}x[100001];
const double prec=pow(10,-12);
int minn=1;
double panta[100001];
pct stiv[100001];
int cur;
int smn;
inline int semn(pct x1, pct x2, pct x3)
{
double det = x1.x*(x2.y-x3.y)+x1.y*(x3.x-x2.x)-x3.x*x2.y+x3.y*x2.x;
if(det>prec)
return 1;
if(det<-prec)
return -1;
if(det<prec)
return 0;
}
bool cmp(const pct x1,const pct x2)
{
if(panta[x1.poz]-panta[x2.poz]>prec)
return true;
else if(abs(panta[x1.poz]-panta[x2.poz])<prec)
if(x1.x-x2.x>prec)
return true;
else if(abs(x1.x-x2.x)<prec)
if(x1.y-x2.y<-prec)
return true;
else return false;
}
inline double dist(int x1, int x2)
{
return sqrt((x[x1].x-x[x2].x)*(x[x1].x-x[x2].x)+(x[x1].y-x[x2].y)*(x[x1].y-x[x2].y));
}
void citire()
{
freopen("infasuratoare.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%lf%lf",&x[i].x,&x[i].y);
x[i].poz=i;}
fclose(stdin);
}
void stab_pornire()
{
for(int i=2;i<=n;++i)
if(x[i].y-x[minn].y<-prec)
minn=i;
else if(abs(x[i].y-x[minn].y)<prec)
if(x[i].x-x[minn].x<-prec)
minn=i;
stiv[++cur]=x[minn];
}
void pante()
{
for(int i=1;i<=n;++i)
if(i!=minn)
panta[i]=((x[i].x-x[minn].x)/dist(minn,i));
}
void infconv()
{
int i;
cur=3;
int p=0;
for(i=1;i<=n;++i)
if(x[i].poz!=stiv[1].poz)
if(abs(x[i].y-stiv[1].y)<prec)
stiv[2]=x[i],p=i;
if(p==0)
{
if(x[1].poz!=stiv[1].poz)
stiv[2]=x[1],p=1;
else stiv[2]=x[2],p=2;
}
stiv[3]=x[p+1];
smn=semn(stiv[1],stiv[2],stiv[3]);
for(int i=p+2;i<=n;++i)
{
if(x[i].poz!=stiv[1].poz){
if(smn!=semn(stiv[cur-1],stiv[cur],x[i]))
stiv[cur]=x[i];
else
stiv[++cur]=x[i];
}
}
}
void afisare()
{
freopen("infasuratoare.out","w",stdout);
printf("%d\n",cur);
for(int i=1;i<=cur;++i)
printf("%lf %lf\n",stiv[i].x,stiv[i].y);
}
int main()
{
citire();
stab_pornire();
pante();
sort(x+1,x+n+1,cmp);
infconv();
afisare();
return 0;
}