11800 - Determine the Shape

[programmin]

I noticed when submitting java code to some previous contest problems, it gives "time limit exceeded". I thought maybe the code just isn't efficient enough, but then I tried a very simple, fast code that only takes input and gives bogus output. I thought it should at least change from "time limit exceeded" to "wrong answer", but this always gives "time limit exceeded":

Code: Select all

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		int[] x = new int[4];
		int[] y = new int[4];
		Scanner sc = new Scanner(System.in);
		int entries = sc.nextInt();
		for (int i=0; i<entries; i++) {
			for (int c=0; c<4; c++) {
				x[c] = sc.nextInt();
				y[c] = sc.nextInt();
			}
			System.out.println("Case 1: Rectangle");
		}
	}
}

The problem I am trying is from the latest contest volume, "11800 - Determine the Shape".

[asraful.ruet]

Hi ,
Someone help me !
I am getting wa !
I failed to find out error of my code .

Code: Select all

#include<stdio.h>
#include<math.h>
int main(){

    int t,i,k,j;
    int x[6],y[6],n;
    double b1,b2,b3,b4,d1,d2,d3,d4,d5,d6;

    scanf("%d",&t);

for(i=1;i<=t;i++){

    for(j=0;j<4;j++)
       scanf("%d %d",&x[j],&y[j]);

    for(j=0;j<3;j++)
     for(k=j+1;k<4;k++){
         if(y[j]>y[k]){
             n=y[j];
             y[j]=y[k];
             y[k]=n;
             n=x[j];
             x[j]=x[k];
             x[k]=n;

             }
        }

    if(x[3]>x[2]){
             n=x[2];
             x[2]=x[3];
             x[3]=n;

             n=y[2];
             y[2]=y[3];
             y[3]=n;
        }

    if(x[0]>x[1]){
             n=x[1];
             x[1]=x[0];
             x[0]=n;
             n=y[1];
             y[1]=y[0];
             y[0]=n;
        }


    b1=(double)pow((pow(x[0]-x[1],2)+pow(y[0]-y[1],2)),.5);
    b2=(double)pow((pow(x[1]-x[2],2)+pow(y[1]-y[2],2)),.5);
    b3=(double)pow((pow(x[2]-x[3],2)+pow(y[2]-y[3],2)),.5);
    b4=(double)pow((pow(x[3]-x[0],2)+pow(y[3]-y[0],2)),.5);

    d1=(double)pow((pow(x[0]-x[2],2)+pow(y[0]-y[2],2)),.5);
    d2=(double)pow((pow(x[1]-x[3],2)+pow(y[1]-y[3],2)),.5);

    d3=(double)(y[0]-y[1])/(double)(x[0]-x[1]);
    d4=(double)(y[2]-y[3])/(double)(x[2]-x[3]);

    d5=(double)(y[1]-y[2])/(double)(x[1]-x[2]);
    d6=(double)(y[3]-y[0])/(double)(x[3]-x[0]);

if(b1==b2&& b3==b4 &&b1==b3 && d1==d2)
 printf("Case %d: Square\n",i);
else if(b1==b3&&b2==b4&&b1!=b2&&d1==d2)
 printf("Case %d: Rectangle\n",i);
else if(b1==b2&& b3==b4 &&b1==b3&&d1!=d2)
 printf("Case %d: Rhombus\n",i);
else if(b1==b3&&b2==b4&&b1!=b2&&d1!=d2)
 printf("Case %d: Parallelogram\n",i);
else if((d3==d4&&d5!=d6)||(d3!=d4&&d5==d6))
 printf("Case %d: Trapezium\n",i);
else
printf("Case %d: Ordinary Quadrilateral\n",i);

}

return 0;
    }

[Angeh]

got many WA's for this simple Problem ...
How should we construct the Shape .... ??
Thanks in advance

[jurajz]

I have 13 RTE's and 3 WA's before AC My idea was make convex hull from the input points and get input points in (counter)clockwise order. I assumed, that 4 points form always convexhull of 4 points - that is not correct.

For input

Code: Select all

1
0 3
-3 0
0 6
3 0

the 4 input points form convex hull of 3 points and the answer is

Code: Select all

Case 1: Ordinary Quadrilateral

Maybe this is reason of your WA's. If not, there are many ways to determine the shape. All you need is length of sides, angles and checking if two sides are parallel. If you use floating-point numbers, you can try check their equality by small epsilon (I assumed epsilon = 10^-9). Hope you will get AC now

[Angeh]

Thanks jurajz ....
i should Try convex ...

Keep Posting ...

[receme]

I cannot find what is wrong. But contiously get WA. Here is my code.

Code: Select all

#include<stdio.h>
#include<math.h>

long i,j,k,n,l,m,t1,t2;
long a1,b1,a2,b2,a3,b3,a4,b4,flag;
 float d1,d2,d3,d4,r1,r2;
 void set();
 int main(){
     
     scanf("%ld",&m);
     
     for(l=0;l<m;l++){
     
      scanf("%ld %ld %ld %ld %ld %ld %ld %ld",&a1,&b1,&a2,&b2,&a3,&b3,&a4,&b4);
       
      
      set();   
      set();
      set();
      set();   
      set();
      set();
      
      
    
      d1= sqrt((a1-a2)*(a1-a2)+(b1-b2)*(b1-b2));   
      d2= sqrt((a2-a3)*(a2-a3)+(b2-b3)*(b2-b3));
      d3= sqrt((a3-a4)*(a3-a4)+(b3-b4)*(b3-b4));
      d4= sqrt((a4-a1)*(a4-a1)+(b4-b1)*(b4-b1));
      r1= sqrt((a1-a3)*(a1-a3)+(b1-b3)*(b1-b3));
      r2= sqrt((a4-a2)*(a4-a2)+(b4-b2)*(b4-b2));
     
    
      if(r1==r2){
                 
       if(d1==d2&&d2==d3&&d3==d4&&d4==d1){
        printf("Case %ld: Square\n",l+1);
        goto x; }
        
       else if(d1==d3&&d2==d4&&d1!=d2){
        printf("Case %ld: Rectangle\n",l+1);
       
       goto x; }
        }
      else{
     
        if(d1==d2&&d2==d3&&d3==d4&&d4==d1){
         printf("Case %ld: Rhombus\n",l+1);
         goto x; }
        else if(d1==d3&&d2==d4&&d1!=d2){
         printf("Case %ld: Parallelogram\n",l+1);
         goto x;}
         }
       
      
      
      if((b1==b2&&b3==b4)||(a1==a4&&a2==a3))
       printf("Case %ld: Trapezium\n",l+1);
      else
       printf("Case %ld: Ordinary Quadrilateral\n",l+1);
       
      x:
      continue;
       }
              
       return 0;
       }
             
           
    void set(){
         if(a1>a2){
       t1=a1; t2=b1;
       a1=a2; b1=b2; 
       a2=t1; b2=t2; }
     
      if(b2>b3){
        t1=b2; t2=a2;
       b2=b3; a2=a3; 
       b3=t1; a3=t2; }
       
      
                    
       if(a4>a3){
        t1=b4; t2=a4;
       b4=b3; a4=a3; 
       b3=t1; a3=t2; }
       
            
       if(b4<b1){
        t1=b4; t2=a4;
       b4=b1; a4=a1; 
       b1=t1; a1=t2; }
       
   
       }
           
      

I don't know anything about convex hull. Can anyone explain it. Give me a link where I will find this algorithm.

[Angeh]

search it on .. http://www.google.com/

[ujjal.ruet]

Hello guys..I am getting RE on 11800.I can't find out the problem.
Actually I have used convex hull to sort the point.
got RE.

Again,I have used another method using the maximum angle of rectangles and Got AC.
why not convex hull???

Here is my RE code.Please check this.

Code: Select all

/////////////convex hull 11800 //////////////////
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define PI 3.141592653589793;
//#define INF 24859675
const int MAXN=5;

typedef struct
{
long double x,y;
}Point;

Point p[MAXN];

Point p0={0,0};


//long double F[5];

long double dis(int a,int b){

return (sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y)));

}


long double comp(int c,int a,int b)
{
long double C,A,B;
C=dis(a,b);
A=dis(c,b);
B=dis(c,a);

//cout<<A<<" "<<B<<" "<<C<<" ";
long double angle=acos(((B*B)+(A*A)-(C*C))/2/A/B)*180/PI;
// cout<<angle<<endl;
//cout<<endl<<endl<<endl;

return angle;
}




bool cmp1(const Point a,const Point b)
{
if( a.y == b.y )
return a.x < b.x;
else
return a.y < b.y;
}

long double xmult(Point p1,Point p2,Point p0)//²?»>0??¹?
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
//return (p1.x*(p2.y-p0.y)-p1.y*(p2.x-p0.x)+(p2.x*p0.y-p0.x*p2.y));

}

bool cmp2(const Point a,const Point b)//¼«½????
{
if( xmult(a,b,p0) < 0 ) return false;
else return true;
}

int main()
{

int i,j;

long double d1,d2,d3,d4,r1,r2,m1,m2,T1,T2,T3,T4,s,m3,m4;

long n = 0,l,c;
//freopen("pp.txt","r",stdin);
scanf("%ld",&l);
for(c=0;c<l;c++){


for(n=0;n<4;n++)
{
//scanf("%lf %lf",&p[n].x,&p[n].y) ;
cin>>p[n].x>>p[n].y;
}


//sort(p+1,p+n,cmp1);
sort(p+1,p+n,cmp2);

//sort(p+1,p+n);


int top = -1,S[MAXN];
S[++top] = 0;
S[++top] = 1;

for( i = 2 ; i < n ; i ++ )//grahamScan?¨?è·¨
{
while( xmult(p[i],p[S[top]],p[S[top-1]]) > 0 )
top --;
S[++top] = i;
}
/*
for( i = 0 ; i <= top ; i ++ )
printf("(%.lf,%.lf)\n",p[i].x,p[i].y);
printf("\n\n");
*/
/*
F[1]=comp(0,3,2);
F[2]=comp(0,1,3);
F[3]=comp(0,1,2);
//cout<<F[1]<<" "<<F[2]<<" "<<F[3]<<endl;

if(F[1]>= F[2]&& F[1]>=F[3])
{
    r1=p[2].x;
    p[2].x=p[1].x;
    p[1].x=r1;

    r2=p[2].y;
    p[2].y=p[1].y;
    p[1].y=r2;

}

//else if(F[2]>= F[1]&& F[2]>=F[3])
//{

//}

else if(F[3]>= F[2]&& F[3]>=F[1])
{
   r1=p[2].x;
    p[2].x=p[3].x;
    p[3].x=r1;

    r2=p[2].y;
    p[2].y=p[3].y;
    p[3].y=r2;


}
*/
//cout<<endl<<p[0].x<<","<<p[0].y<<endl<<p[1].x<<","<<p[1].y<<endl<<p[2].x<<","<<p[2].y<<endl<<p[3].x<<","<<p[3].y<<endl;





d1= dis(0,1);
d2= dis(1,2);



T1=comp(0,1,3);
T2=comp(1,2,0);
T3=comp(2,1,3);
T4=comp(3,0,2);

if(T1==T2&&T2==T3&&T1==T4){
    if(d1==d2)
      printf("Case %ld: Square\n",c+1);
    else
        printf("Case %ld: Rectangle\n",c+1);

    }

else if(T1==T3&&T2==T4){
    if(d1==d2)
     printf("Case %ld: Rhombus\n",c+1);
    else
      printf("Case %ld: Parallelogram\n",c+1);

    }


else{
/*
if(p[0].x-p[1].x==0)
 m1=INF;
else
m1=(p[0].y-p[1].y)/(p[0].x-p[1].x);

if(p[3].x-p[2].x==0)
 m2=INF;
else
  m2=(p[3].y-p[2].y)/(p[3].x-p[2].x);

if(p[0].x-p[3].x==0)
 m3=INF;
else
m3=(p[0].y-p[3].y)/(p[0].x-p[3].x);

if(p[1].x-p[2].x==0)
 m4=INF;
else
  m4=(p[1].y-p[2].y)/(p[1].x-p[2].x);





if(m1==m2&&m3!=m4)
printf("Case %ld: Trapezium\n",c+1);
else
printf("Case %ld: Ordinary Quadrilateral\n",c+1);
*/



s=0;

if(p[0].x==p[3].x && p[1].x==p[2].x)
   s=1;

if(p[3].x==p[2].x&&p[0].x==p[1].x)
   s=1;

if(p[0].y==p[3].y&&p[1].y==p[2].y)
   s=1;

if(p[3].y==p[2].y&&p[0].y==p[1].y)
   s=1;

if(s!=1){
    if(p[0].x!=p[3].x && p[1].x!=p[2].x){

        m1=(p[0].y-p[3].y)/(p[0].x-p[3].x);
        m2=(p[1].y-p[2].y)/(p[1].x-p[2].x);
        if(m1==m2)
          s=1;
        }

if(p[3].x!=p[2].x && p[0].x!=p[1].x){
        m1=(p[3].y-p[2].y)/(p[3].x-p[2].x);
        m2=(p[0].y-p[1].y)/(p[0].x-p[1].x);
        if(m1==m2)
          s=1;
        }



       }
if(s==1)
printf("Case %ld: Trapezium\n",c+1);
else
printf("Case %ld: Ordinary Quadrilateral\n",c+1);

    }


}

return 0;
}
[color=#4040FF][/color]

[ujjal.ruet]

Hey guys,I have avoided RE.Now getting TLE.
For what,I don't know...please help me....

Code: Select all

///////Determine the shape 11800 //////////////////
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define PI 3.141592653589793;

const int MAXN=5;

typedef struct
{
long double x,y;
}Point;

Point p[MAXN];

Point p0={0,0};




long double dis(int a,int b){

return (sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y)));

}





long double DHAL(int a, int b)
{
long double y1=p[a].y-p[b].y;
long double x1=p[a].x-p[b].x;
long double m=y1/x1;
return m;
}


bool PARAX(int a, int b)
{
if(p[a].x==p[b].x)
return 1;
else return 0;

}

bool PARAY(int a, int b)
{
if(p[a].y==p[b].y)
return 1;
else return 0;

}









long double comp(int c,int a,int b)
{
long double C,A,B;
C=dis(a,b);
A=dis(c,b);
B=dis(c,a);

long double angle=acos(((B*B)+(A*A)-(C*C))/2/A/B)*180/PI;

return angle;
}




bool cmp1(const Point a,const Point b)
{
if( a.y == b.y )
return a.x < b.x;
else
return a.y < b.y;
}

long double xmult(Point p1,Point p2,Point p0)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);

}

bool cmp2(const Point a,const Point b)
{
if( xmult(a,b,p0) < 0 ) return false;
else return true;
}

int main()
{

int i,j;

long double d1,d2,d3,d4,r1,r2,m1,m2,T1,T2,T3,T4,state,m3,m4;

long n = 0,l,c;
scanf("%ld",&l);
for(c=0;c<l;c++){


for(n=0;n<4;n++)
{
cin>>p[n].x>>p[n].y;
}


sort(p+1,p+n,cmp1);
sort(p+1,p+n,cmp2);


for(int n=0;n<4;n++)
{
cout<<p[n].x<<"    "<<p[n].y<<endl;
}



d1= dis(0,1);
d2= dis(1,2);
d3=dis(2,3);
d4=dis(3,0);


T1=comp(0,1,3);
T2=comp(1,2,0);
T3=comp(2,1,3);
T4=comp(3,0,2);

if(T1==T2&&T2==T3&&T1==T4){
    if(d1==d2)
      printf("Case %ld: Square\n",c+1);
    else
        printf("Case %ld: Rectangle\n",c+1);

    }

else if(T1==T3&&T2==T4){
    if(d1==d2)
     printf("Case %ld: Rhombus\n",c+1);
    else
      printf("Case %ld: Parallelogram\n",c+1);

    }


else{
  state=0;


if(PARAX(0,3)==1 && PARAX(1,2)==1)

{
state=1;
}

if(PARAX(3,2)==1 && PARAX(0,1)==1)
{
state=1;
}

if(PARAY(0,3)==1 && PARAY(1,2)==1)

{
state=1;
}

if(PARAY(3,2)==1 && PARAY(0,1)==1)
{
state=1;
}

if(state!=1)
{
if(PARAX(0,3)==0 && PARAX(1,2)==0)
{
m1=DHAL(0,3);
m2=DHAL(1,2);
if(m1==m2)
state=1;
}

if(PARAX(3,2)==0 && PARAX(0,1)==0)
{
m1=DHAL(3,2);
m2=DHAL(0,1);
if(m1==m2)
state=1;
}



}

if(state==1)
printf("Case %ld: Trapezium\n",c+1);


else
 printf("Case %ld: Ordinary Quadrilateral\n",c+1);


    }


}

return 0;
}

[SePulTribe]

Hi guys. I finally solved it after 11 tries! No need for anything fancy. Use long long and make sure EVERYTHING is done in long long. Don't use any double or it'll fail (I think there are test cases that involve vectors that are very very small degrees apart, thereby causing problems with floating point arithmetic). Use the dot product and cross products only. No need for any convex hull algorithm. Use an integer-based ccw to sort the points into order. Good luck!

[surya ss]

hello, i try this problem using long no double or floating point involved, but i got WA
is there anything I need to concern ?
any one can help me find what make my code WA, thanks
this is my code:

Code: Select all

removed

[surya ss]

I tried using simplest approach:
sort the four position using ccw sorting by cross product
check the 90 degree by using trigonometry:
AC^2 = AB^2 + BC^2 - 2(AB)(BC)cos d
since cos 90 = 0
then AC^2 = AB^2 + BC^2
i check the four side from the position

the following is the check :
1. if all 4 is 90 degree :
a. if all four side has same length => square
b. if opposite side has same length => rectangle
2. if all 4 is not 90 degree:
a. if all four side has same length => Rhombus
b. if opposite side has same length => Parallelogram
3. if opposite side is parallel and the other is not => Trapezium
4. other => Ordinary Quadrilateral

is anybody can tell me what wrong with this logic or with my code?

here is my code:

Code: Select all

removed

[robot]

Hi.. Surya..
Actually i don't see ur code..but from ur explanation i think something is wrong..
you can forward below this approach..
1.if 4 arm length is equal
if 4 angle is 90 --> square
else ---> Rhombus
2. if (2 * 2)opposite arm length is equal
if 4 angle is 90 --->Rectangle
else---->Parallelogram
3. if no arm length are equal but if opposite side is parallel other is not -->Trapezium
else-->Ordinary Quadrilateral
I hope it will be helped you..
ASU(SUST)

[surya ss]

Hi.. Surya..
Actually i don't see ur code..but from ur explanation i think something is wrong..
you can forward below this approach..
1.if 4 arm length is equal
if 4 angle is 90 --> square
else ---> Rhombus
2. if (2 * 2)opposite arm length is equal
if 4 angle is 90 --->Rectangle
else---->Parallelogram
3. if no arm length are equal but if opposite side is parallel other is not -->Trapezium
else-->Ordinary Quadrilateral
I hope it will be helped you..
ASU(SUST)

Thank you for your help
I've tried according to your suggestion, but still not right, there's must be something wrong with my implementation in:
1. sorting the point
2. check 90 degree
3. check parallel

my implementation in check parallel is :
dy1 = ( y1 - y2 ) of line 1
dx1 = ( x1 - x2 ) of line 1
dy2 = ( y1 - y2 ) of line 2
dx2 = ( x1 - x2 ) of line 2

ay = dy1 / gcd(dx1,dy1)
ax = dx1 / gcd(dx1,dy1)
by = dy2 / gcd(dx2,dy2)
bx = dx2 / gcd(dx2,dy2)
parallel if (ay==0 && by==0) || (ax==0 && bx==0) || (ax==bx && ay==by)

is there anything wrong with this implementation?
I tried it using this I/O:
Input:

Code: Select all

13
1 0
2 1
1 2
0 1
0 0
3 0
3 2
0 2
0 0
8 4
5 0
3 4
0 0
2 0
3 2
1 2
0 0
5 0
4 3
1 3
0 0
5 0
4 3
1 4
0 3
-3 0
0 6
3 0
0 1
1 0
1 1
2 1
1 0
10 0
5 3
-5 3
0 0
10 0
13 3
3 3
0 0
10 0
15 3
3 3
2 1
0 0
1 2
0 0
10000 -10000
-10000 -10000
-10000 10000
10000 10000

Output:

Code: Select all

Case 1: Square
Case 2: Rectangle
Case 3: Rhombus
Case 4: Parallelogram
Case 5: Trapezium
Case 6: Ordinary Quadrilateral
Case 7: Ordinary Quadrilateral
Case 8: Ordinary Quadrilateral
Case 9: Trapezium
Case 10: Parallelogram
Case 11: Trapezium
Case 12: Ordinary Quadrilateral
Case 13: Square

This is my new code:

Code: Select all

AC

[robot]

Hi suraya...
For ur input my accepted output is given...
Case 1: Square
Case 2: Rectangle
Case 3: Rhombus
Case 4: Parallelogram
Case 5: Trapezium
Case 6: Ordinary Quadrilateral
Case 7: Ordinary Quadrilateral
Case 8: Ordinary Quadrilateral
Case 9: Trapezium
Case 10: Parallelogram
Case 11: Trapezium
Case 12: Trapezium
Case 13: Square
may be some output don't match like me...
I think ur Trapezium condition exactly not right..
if u check parallel , u can use simply vector Cross Product...if Cross product is zero , then parallel , otherwise not..
ASU(SUST)