Pagini recente » Cod sursa (job #1809310) | Cod sursa (job #66252) | Cod sursa (job #1114996) | Cod sursa (job #2802500) | Cod sursa (job #457121)
Cod sursa(job #457121)
#include<fstream>
#include<math.h>
using namespace std;
# define nmax 1502
double rad3=1.7320508;
double precision=0.001;
typedef struct structura{double x,y;};
structura p[nmax],aux;
int n;
ifstream f("triang.in");
ofstream g("triang.out");
void read()
{
f>>n;int i;
for(i=1;i<=n;i++) f>>p[i].x>>p[i].y;
}
void swap(int a,int b)
{
structura aux=p[a];p[a]=p[b];p[b]=aux;
}
void DownHeap(int from,int to)
{
for(int son=2*from;son<to;from=son,son=from*2)
{
if(son<to-1&&(p[son].x<p[son+1].x||(p[son].x==p[son+1].x&&p[son].y<p[son+1].y))) son++;
if(p[from].x>=p[son].x||(p[from].x==p[son].x&&p[from].y>=p[son].y)) return;
swap(from,son);
}
}
void HeapSort(int from,int to)
{
int i;
for(i=(to-from)/2;i>0;i--) DownHeap(i,to);
while(from<to)
{
swap(from,to-1);to--;
DownHeap(from,to);
}
}
double absolut(double d)
{
if(d<0)return -d;
return d;
}
int search(double a,double b,int st)
{
int dr=n,mij;
do
{
mij=(st+dr)/2;
if(absolut(p[mij].x-a)<precision&&absolut(p[mij].y-b)<precision)return 1;
if(p[mij].x<a||(p[mij].x==a&&p[mij].y<b)) st=mij+1;
else dr=mij;
}while(st<dr);
return 0;
}
int main()
{
int nr=0,i,j;
structura x1,x2;
double zx,zy;
read();
HeapSort(1,n+1);
for(i=1;i<n-1;i++)
for(j=i+1;j<n;j++)
{
zx=p[j].x-p[i].x;zy=p[j].y-p[i].y;
x1.x=(zx-zy*rad3)/2+p[i].x;x1.y=(zx*rad3+zy)/2+p[i].y;
x2.x=(zx+zy*rad3)/2+p[i].x;x2.y=(zy-zx*rad3)/2+p[i].y;
if(search(x1.x,x1.y,j+1))nr++;
if(search(x2.x,x2.y,j+1))nr++;
}
g<<nr<<'\n';
}