10979 - How Many Triangles?

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

moon
New poster
Posts: 5
Joined: Mon Jan 02, 2006 12:49 pm
Contact:

heeeeeeeeelp

Post by moon » Thu Aug 31, 2006 11:55 am

i got WA. the test cases in this post is ok to my code

here is my code

plz plz someone help me


[cod#include<stdio.h>
#include<math.h>
#include<stdlib.h>

int fun(double x1,double x2,double x3,double x4,double y1,double y2,double y3,double y4)
{
double a1 = y1-y2;
int t=0;
double b1 = -(x1-x2);
double c1 = (y1*(x1-x2))-(x1*(y1-y2));

double d1 = (a1*x3) + (b1*y3) + c1;
double d2 = (a1*x4) + (b1*y4) + c1;

if((x1==x3&&y1==y3) || (x1==x4&&y1==y4) || (x2==x3&&y2==y3) || (x2==x4&&y2==y4))
{
t=1;
}
else if((d1>=0 && d2<0) || (d2>=0&& d1<0) ||(d1==0&&d2>0) || (d2==0 && d1>0))
{
double a2 = y3-y4;
double b2 = -(x3-x4);
double c2 = (y3*(x3-x4))-(x3*(y3-y4));

double d3 = (a2*x1) + (b2*y1) + c2;
double d4 = (a2*x2) + (b2*y2) + c2;

if((d3>=0 && d4<0) || (d4>=0&& d3<0))
t= 1;
else if(((d1>=0 && d2<0) || (d2>=0&& d1<0)) && ((d3==0&&d4>0) && (d4==0&&d3>0)))
t=1;
}
return t;
}

int fun02(double x1,double x2,double x3,double x4,double y1,double y2,double y3,double y4 ,int i,int j)
{
int t1=0;
if(x1 != 1000 && x3 != 1000)
{
double s,t;
if( x1-x2==0)
s=90;
else
s = (y1 - y2)/(x1-x2);
if( x3-x4==0)
t=90;
else
t = (y3 - y4)/(x3-x4);
if(s==t && j != i)
{
double a1 = y1-y2;
double b1 = -(x1-x2);
double a2 = y3-y4;
double b2 = -(x3-x4);
double c1 = (y1*(x1-x2))-(x1*(y1-y2));
double c2 = (y3*(x3-x4))-(x3*(y3-y4));
if(c1==c2|| (c1/sqrt(a1*a1 + b1*b1))==(c2/sqrt(a2*a2+b2*b2)))
{
if(x1<x2)
{
if(x1<= x3 && x3<=x2)
t1=1;

else if(x1<=x4 && x4<=x2)
t1=1;

}
else
{
if(x1<= x3 && x3<=x2)
t1=1;

else if(x1<=x4 && x4<=x2)
t1=1;


}
if(x3<x4)
{
if(x1<= x3 && x3<=x2)
t1=1;

else if(x1<=x4 && x4<=x2)
t1=1;


}
else
{
if(x1<= x3 && x3<=x2)
t1=1;

else if(x1<=x4 && x4<=x2)
t1=1;


}
}
}
}
return t1;
}

int main()
{
int n1;
while(scanf("%d",&n1)==1)
{
double arr[11][5] ,brr[11][5];
int c=0;
for(int i=0 ; i< n1 ;i++)
{
scanf("%lf%lf%lf%lf",&brr[0] ,&brr[1],&brr[2],&brr[3]);
}

for(int i=0 ; i<n1 ; i++)
{
for(int j= 0; j< n1 ; j++)
{
double x1=brr[0],x2=brr[2],x3=brr[j][0],x4=brr[j][2];
double y1=brr[1],y2=brr[3],y3=brr[j][1],y4=brr[j][3];
int t1 = fun02(x1,x2,x3,x4,y1,y2,y3,y4 ,i,j);
if(t1==1)
{
double d[7],max=0,max1=0,X1=0,Y1=0,X2=0,Y2=0;
d[1] = abs(x1-x2);
if(d[1]>=max && max1<=(abs(y1-y2)))
{
max=d[1];
max1 =abs(y1-y2);
X1=x1,Y1=y1,X2=x2,Y2=y2;
}
d[2]=abs(x1-x3);
if(d[2]>=max && max1<=(abs(y1-y3)))
{
max=d[2];
max1 =abs(y1-y3);
X1=x1,Y1=y1,X2=x3,Y2=y3;
}
d[3]=abs(x1-x4);
if(d[3]>=max && max1<=(abs(y1-y4)))
{
max=d[3];
max1 =abs(y1-y4);
X1=x1,Y1=y1,X2=x4,Y2=y4;
}
d[4]=abs(x2-x3);
if(d[4]>=max && max1<=(abs(y2-y3)))
{
max=d[4];
max1 =abs(y2-y3);
X1=x2,Y1=y2,X2=x3,Y2=y3;
}
d[5]=abs(x2-x4);
if(d[5]>=max && max1<=(abs(y2-y4)))
{
max=d[5];
max1 =abs(y2-y4);
X1=x2,Y1=y2,X2=x4,Y2=y4;
}
d[6]=abs(x3-x4);
if(d[6]>=max && max1<=(abs(y3-y4)))
{
max=d[6];
max1 =abs(y3-y4);
X1=x3,Y1=y3,X2=x4,Y2=y4;
}
brr[0]=X1,brr[1]=Y1,brr[i][2]=X2,brr[i][3]=Y2;
brr[j][0]=brr[j][1]=brr[j][2]=brr[j][3]=1000;
}
}
}
int n=0;
for(int i=0; i<n1;i++)
{
if(brr[i][0]<1000)
{
arr[n][0]=brr[i][0];
arr[n][1]=brr[i][1];
arr[n][2]=brr[i][2];
arr[n][3]=brr[i][3];
n++;
}
}

for(int i =0 ;i< n; i++)
{
for(int j=i+1 ; j<n;j++)
{
double x1=arr[i][0],x2=arr[i][2],x3=arr[j][0],x4=arr[j][2];
double y1=arr[i][1],y2=arr[i][3],y3=arr[j][1],y4=arr[j][3];
int r = fun(x1,x2,x3,x4,y1,y2,y3,y4);
if(r==1)
{
for(int k=j+1;k<n;k++)
{
x1=arr[i][0],x2=arr[i][2],x3=arr[k][0],x4=arr[k][2];
y1=arr[i][1],y2=arr[i][3],y3=arr[k][1],y4=arr[k][3];
double a1 = y1-y2;
double b1 = -(x1-x2);
double c1 = (y1*(x1-x2))-(x1*(y1-y2));
double a2 = y3-y4;
double b2 = -(x3-x4);
double c2 = (y3*(x3-x4))-(x3*(y3-y4));

int r1=fun(x1,x2,x3,x4,y1,y2,y3,y4);

x1=arr[j][0],x2=arr[j][2],x3=arr[k][0],x4=arr[k][2];
y1=arr[j][1],y2=arr[j][3],y3=arr[k][1],y4=arr[k][3];
double a3 = y1-y2;
double b3 = -(x1-x2);
double c3 = (y1*(x1-x2))-(x1*(y1-y2));

int r2=fun(x1,x2,x3,x4,y1,y2,y3,y4);
double q = (a1*(b2*c3-b3*c2)) + (b1*(a3*c2-a2*c3)) + (c1*(a2*b3-a3*b2));

if(r1==1 && r2==1 && q !=0)
{
c++;

}
}
}

}
}
printf("%d\n",c);
}
return 0;
}

e][/code]
moon

Post Reply

Return to “Volume 109 (10900-10999)”