Pagini recente » Cod sursa (job #833922) | Cod sursa (job #349109) | Cod sursa (job #2609441) | Cod sursa (job #1709955) | Cod sursa (job #1026088)
#include<fstream>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#define rad3 1.73205081
using namespace std;
ifstream f("triang.in");
ofstream g("triang.out");
struct punct
{
double x,y;
};
int n,nr=0,i,j,deb;
punct v[1501],test1,test2,mid;
double panta,a,b,c,eps=10e-4,aux1,aux2;
int cmp(punct a, punct b)
{
if(a.x-b.x<eps&&a.x-b.x>-eps)
{if(a.y-b.y<eps&&a.y-b.y>-eps)
return 0;
else
if(a.y-b.y>eps)
return 1;
else return -1;
}
if(a.x-b.x>eps)
return 1;
return -1;
}
void qksort(int st,int dr)
{int p=st,q=dr;
double temp;
punct piv,aux;
piv=v[p+rand()%(q-p+1)];
while(p<=q)
{
while(v[p].x<piv.x)
p++;
while(v[q].x>piv.x)
q--;
if(p<=q)
{
aux=v[p];v[p]=v[q];v[q]=aux;
if(v[p].x==v[q].x)
if(v[p].y>v[q].y)
{temp=v[p].y;v[p].y=v[q].y;v[q].y=temp;}
p++;q--;
}
}
/*for(deb=1;deb<=n;deb++)
g<<v[deb].x<<" ";
g<<'\n';
for(deb=1;deb<=n;deb++)
g<<v[deb].y<<" ";
g<<'\n'<<'\n';*/
if(st<q)
qksort(st,q);
if(p<dr)
qksort(p,dr);
}
bool caut_bin(int st,int dr,punct k)
{int m;
while(st<=dr)
{
m=(st+dr)/2;
if(cmp(v[m],k)==0)
return 1;
else
if(cmp(v[m],k)<0)
st=m+1;
else
dr=m-1;
}
return 0;
}
void ec_gr2(double a,double b,double c)
{
double delta=pow(b,2)-4*a*c;
test1.x=(-b+sqrt(delta))/(2*a);
test2.x=(-b-sqrt(delta))/(2*a);
}
int main()
{
srand(time(0));
f>>n;
for(i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
qksort(1,n);
//g<<'\n'<<'\n';
for(i=1;i<=n-1;i++)
for(j=i+1;j<=n;j++)
{
mid.x=(v[i].x+v[j].x)/2;
mid.y=(v[i].y+v[j].y)/2;
if(v[j].y-v[i].y==0)
{
test1.x=test2.x=mid.x;
test1.y=mid.y+rad3*mid.x;
test2.y=mid.y-rad3*mid.x;
}
else
{
//g<<"panta e:"<<panta<<" ";
panta=(v[i].x-v[j].x)/(v[j].y-v[i].y);
aux1=pow(v[j].y-v[i].y,2);
aux2=pow(v[j].x-v[i].x,2);
aux1+=aux2;
a=1+pow(panta,2); //g<<"a="<<a<<" ";
b=-2*v[i].x+2*panta*mid.y-2*pow(panta,2)*mid.x-2*panta*v[i].y;// g<<"b="<<b<<" ";
c=pow(mid.y,2)+pow(panta,2)*pow(mid.x,2)-2*mid.x*mid.y*panta-2*mid.y*v[i].y+2*panta*mid.x*v[i].y+pow(v[i].y,2)-aux1+pow(v[i].x,2); //g<<"c="<<c<<" ";
ec_gr2(a,b,c);
test1.y=panta*test1.x+mid.y-panta*mid.x;
test2.y=panta*test2.x+mid.y-panta*mid.x;
}
if(caut_bin(1,n,test1))
nr++;
if(caut_bin(1,n,test2))
nr++;
// g<<test1.x<<" "<<test1.y<<" "<<test2.x<<" "<<test2.y<<'\n'<<'\n';
}
// g<<'\n';
g<<nr/3;
f.close();g.close();
}