Pagini recente » Cod sursa (job #180904) | Cod sursa (job #1000604) | Cod sursa (job #901301) | Cod sursa (job #892132) | Cod sursa (job #441950)
Cod sursa(job #441950)
#include<fstream>
#include<math.h>
#define dmax 1503
#define erm 0.001
using namespace std;
ifstream in("triang.in");
ofstream out("triang.out");
int n,sol;
double x1,y11,x2,y2;
struct point
{ double x;
double y;
} p[dmax];
typedef int (*compfn)(const void *,const void *);
double dist(int i,int j)
{ return sqrt( (p[i].x - p[j].x)*(p[i].x - p[j].x) + ( p[i].y - p[j].y)*(p[i].y - p[j].y) );
}
int sf(struct point *a,struct point *b)
{ if(a->x != b->x)
{ if(a->x > b->x)
return 1;
if(a->x < b->x)
return -1;
return 0;
}
if(a->y > b->y)
return 1;
if(a->y < b->y)
return -1;
return 0;
}
double absl(double k)
{ double s;
s=k;
if(k<0)
s=(-1)*k;
return s;
}
void bin_search(int i,int j,double xx,double yy)
{ int l,r,m;
l=i+1;
r=j-1;
while(l<=r)
{ m=(l+r)/2;
if(absl(p[m].x - xx) <= erm)
{ if(absl(p[m].y - yy) <=erm)
{ sol++;
//out<<i<<" "<<j<<" "<<m<<'\n';
return;
}
else if(p[m].y < yy)
while(p[m].y < yy)
{ if(absl(p[m].y - yy) <=erm && absl(p[m].x - xx) <= erm)
{ sol++;
//out<<i<<" "<<j<<" "<<m<<'\n';
return;
}
m++;
}
else if(p[m].y > yy)
while(p[m].y > yy)
{ if(absl(p[m].y - yy) <=erm && absl(p[m].x - xx) <= erm)
{ sol++;
//out<<i<<" "<<j<<" "<<m<<'\n';
return;
}
m--;
}
return;
}
else if(p[m].x < xx && xx-p[m].x > erm)
l=m+1;
else if(p[m].x > xx && p[m].x - xx > erm)
r=m-1;
}
}
void coord(int i,int j)
{ double dst,sn,cs,xmij,ymij,h;
dst=dist(i,j);
sn=absl(p[i].y - p[j].y) / dst;
cs=(p[j].x - p[i].x) / dst;
xmij=(p[i].x+p[j].x)/2;
ymij=(p[i].y+p[j].y)/2;
h=(dst/2)*sqrt(3);
x1=xmij-h*sn;
y11=ymij+h*cs;
x2=xmij+h*sn;
y2=ymij-h*cs;
}
int main()
{ int i,j;
in>>n;
for(i=0;i<n;i++)
in>>p[i].x>>p[i].y;
in.close();
qsort( (void*)&p, n, sizeof(struct point), (compfn)sf );
for(i=2;i<n;i++)
for(j=0;j<i-1;j++)
{ coord(j,i);
bin_search(j,i,x1,y11);
bin_search(j,i,x2,y2);
}
out<<sol;
out.close();
return 0;
}