Pagini recente » Cod sursa (job #3178228) | Cod sursa (job #773342)
Cod sursa(job #773342)
#include<iostream>
#include<cmath>
#include<fstream>
#include<algorithm>
using namespace std;
const double Error=0.0001;
struct punct{double x,y;};
struct dre{double a,b,c;};
punct a[1600],M;
int n,sol;
int st,dr;
int cmp(punct A, punct B)
{
if (A.x<B.x)
return 1;
if (A.x==B.x)
if (A.y<B.y)
return 1;
return 0;
}
void ec_dr(punct a, punct b, dre & ab)
{
ab.a=b.y-a.y;
ab.b=a.x-b.x;
ab.c=a.x*a.y-a.x*b.y+a.y*b.x-a.y*a.x;
}
void ec2(double a, double b, double c,double &x1, double &x2)
{
x1=(-b+sqrt(b*b-4*a*c))/(2*a);
x2=(-b-sqrt(b*b-4*a*c))/(2*a);
}
double fabs( double x)
{
if (x<0)
return -x;
return x;
}
double dist (punct a, punct b)
{
return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int cauta (punct A)
{
while (st<=dr)
{
int mij;
mij=(st+dr)/2;
if (fabs(a[mij].x-A.x)<=Error)
if (fabs(a[mij].y-A.y)<=Error)
return 1;
if (fabs(a[mij].x-A.x)<=Error)
if (a[mij].y<A.y+Error)
st=mij+1;
else
if (a[mij].y>A.y)
dr=mij-1;
else
if (a[mij].x<A.x)
st=mij+1;
else
if (A.x>a[mij].y)
dr=mij-1;
}
return 0;
}
int main(void)
{
fstream f,g;
f.open("triang.in",ios::in);
g.open("triang.out",ios::out);
f>>n;
int i,j;
double rad=sqrt(3+0.0)/2,l1,m1,Dist,m2,l2,l3;
for (i=1;i<=n;i++)
f>>a[i].x>>a[i].y;
sort(a+1,a+1+n,cmp);
for (i=1;i<=n-2;i++)
for (j=i+1;j<=n-1;j++)
{
l1=dist(a[i],a[j]);
dre d;
ec_dr(a[i],a[j],d);
if (d.b!=0)
{
double A=(a[i].x+a[j].x)/2,B=(a[i].y-a[j].y)/2;
double k=3/4*l1*l1,x,y,x1;
m1=(-1*d.a/d.b);
if (m1==0)
m2=0;
else
m2=-1/m1;
st=j+1;
dr=n;
dre d2;
d2.a=m2;
d2.b=-1;
d2.c=B-m2*A;
ec2(d2.b*d2.b+d2.a*d2.a,-2*A*d2.b*d2.b+2*d2.a*d2.c+B*d2.b*d2.a,A*A*d2.b*d2.b+d2.c*d2.c+B*d2.b*d2.c+B*B*d2.b*d2.b-k*d2.b*d2.b,x,x1);
if (x>=a[j].x)
{
punct w;
w.x=x;
w.y=(-d2.c-d2.a*x)/d2.b;
if (cauta(w))
{
sol++;
break;
}
}
else
if (x1>=a[j].x)
{
x=x1;
punct w;
w.x=x;
w.y=(-d2.c-d2.a*x)/d2.b;
if (cauta(w))
{
sol++;
break;
}
}
}
}
g<<sol;
}