Pagini recente » Cod sursa (job #2939913) | Cod sursa (job #288982) | Cod sursa (job #2850486) | Cod sursa (job #2772509) | Cod sursa (job #57307)
Cod sursa(job #57307)
using namespace std;
#include<fstream>
#include<math.h>
#define Nmax 1506
double x[Nmax],y[Nmax],eps=0.001;
int b1,N;
double modul(double x)
{
if(x<0) return -x;
return x;
}
int search(double x0,double y0,int j)
{
int li=j+1,lf=N,i;
while(li<=lf)
{
i=(li+lf)>>1;
if(modul(x[i]-x0)<eps && modul(y[i]-y0)<eps)
return 1;
else
if(modul(x[i]-x0)<eps)
{
if(y[i] < y0-eps)
li=i+1;
else
lf=i-1;
}
else
if(x[i] < x0-eps)
li=i+1;
else
lf=i-1;
}
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;
}