Pagini recente » Cod sursa (job #1064020) | Cod sursa (job #926620) | Cod sursa (job #2356542) | Cod sursa (job #2205399) | Cod sursa (job #57299)
Cod sursa(job #57299)
using namespace std;
#include<fstream>
#include<math.h>
#define Nmax 1506
#define eps 0.001
double x[Nmax],y[Nmax];
int b1,N;
double modul(double x)
{
if(x<0) return -x;
return x;
}
int search(double x0,double y0,int j)
{
int ind=0,i;
for(i=b1;i;i>>=1)
if( x[ind+i] <= x0 )
ind+=i;
i=ind;
while(i && modul(x[i]-x0) < eps )
{
if( modul(y[i]-y0) <eps && ind>j)
return 1;
i--;
}
i=ind;
while(i<=N &&modul(x[i]-x0) < eps )
{
if( modul(y[i]-y0) <eps && ind>j)
return 1;
i++;
}
return 0;
}
void intersc(int i,int j)
{
double aux;
aux=x[i];
x[i]=x[j];
x[j]=aux;
aux=y[i];
y[i]=y[j];
y[j]=aux;
}
int comp(int i,int j)
{
if(x[i]<x[j])
return -1;
if(x[i]>x[j])
return 1;
if(y[i]<y[j])
return -1;
if(y[i]>y[j])
return 1;
return 0;
}
int main()
{
ifstream fin("triang.in");
ofstream fout("triang.out");
int i,j,k;
double rad=1.73205;
fin>>N;
b1=1;
while( b1 <= N ) b1<<=1;
b1>>=1;
for(i=1;i<=N;i++)
fin>>x[i]>>y[i];
for(i=1;i<=N;i++)
{
j=i;
while(j/2 && comp(j/2,j)<0 )
{
intersc(j/2,j);
j/=2;
}
}
i=N;
while(i>1)
{
intersc(1,i);
i--;
j=1;
while(1)
{
k=j<<1;
if(k>i) break;
if(k+1<=i && comp(k,k+1)<0 ) k++;
if(comp(j,k)>=0) break;
intersc(j,k);
j=k;
}
}
//calculare
int sol=0;
double p,xm,ym,x0,y0,d,dif,A,B,C,delta,p1,p2;
for(i=1;i<N;i++)
for(j=i+1;j<=N;j++)
{
xm=(x[i]+x[j])/2.0;
ym=(y[i]+y[j])/2.0;
if( modul(x[i] - x[j]) < eps)
{
d=modul(y[i]-y[j]);
x0=xm;
dif=(d*rad)/2.0;
y0=ym+dif;
if(search(x0,y0,j))
sol++;
y0=ym-dif;
if(search(x0,y0,j))
sol++;
}
else
if( modul(y[i] - y[j]) < eps)
{
d=modul(x[i]-x[j]);
y0=ym;
dif=d*rad/2.0;
x0=xm+dif;
if(search(x0,y0,j))
sol++;
x0=xm-dif;
if(search(x0,y0,j))
sol++;
}
else
{
p=(y[j]-y[i])/(x[j]-x[i]);
p=(-1.0)/p;
d=(x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
dif=ym-p*xm-y[i];
A=p*p+1.0;
B=2*p*dif-2*x[i];
C=x[i]*x[i] + dif*dif - d;
delta=B*B-4*A*C;
delta=sqrt(delta);
x0= (-B + delta)/(2.0*A);
y0= p*x0+ym-p*xm;
if(search(x0,y0,j))
sol++;
x0= (-B-delta)/(2.0*A);
y0= p*x0+ym-p*xm;
if(search(x0,y0,j))
sol++;
}
}
fout<<sol<<"\n";
fin.close();
fout.close();
return 0;
}