Pagini recente » Cod sursa (job #1428020) | Cod sursa (job #1695181) | Cod sursa (job #2874038) | Cod sursa (job #740324) | Cod sursa (job #441706)
Cod sursa(job #441706)
#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;
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;
}
void bin_search(int i,int j)
{ int l,r,m;
l=i;
r=j;
while(l<r)
{ m=(l+r)/2;
if( max(dist(i,m) - dist(j,m) , dist(j,m) - dist(i,m) ) <=erm )
{ if( max(dist(i,j) - dist(j,m) , dist(j,m) - dist(i,j) ) <= erm)
sol++;
return;
}
else if(dist(i,m) < dist(j,m) )
l=m+1;
else if(dist(i,m) > dist(j,m) )
r=m;
}
}
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=1;i<n;i++)
for(j=0;j<i;j++)
bin_search(j,i);
out<<sol;
out.close();
return 0;
}