Pagini recente » Cod sursa (job #2696652) | Cod sursa (job #3194918) | Cod sursa (job #2479739) | Cod sursa (job #846279) | Cod sursa (job #457117)
Cod sursa(job #457117)
#include<fstream>
#include<math.h>
using namespace std;
# define nmax 1502
# define rad3 1.7320508
# define 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);
}
}
int search(double a,double b,int st)
{
int dr=n,mij;
do
{
mij=(st+dr)/2;
if(abs(p[mij].x-a)<precision&&abs(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;
read();
HeapSort(1,n+1);
for(i=1;i<n-1;i++)
for(j=i+1;j<n;j++)
{
x1.x=(p[i].x+p[j].x-(p[i].y-p[j].y)*rad3)/2;
x1.y=((p[i].x-p[j].x)*rad3+p[i].y+p[j].y)/2;
x2.x=(p[i].x+p[j].x+(p[i].y-p[j].y)*rad3)/2;
x2.y=(p[i].y+p[j].y-(p[i].x-p[j].x)*rad3)/2;
if(search(x1.x,x1.y,j+1))nr++;
if(search(x2.x,x2.y,j+1))nr++;
}
g<<nr<<'\n';
}