Page 3 of 4

Re: 11800 - Determine the Shape

Posted: Fri Aug 29, 2014 10:42 pm
by sabbir_alam_ufo
Why I am getting WA? Anyone help please !!! And isn't the sample output for the third test case is wrong ? It should print Parallelogram but they printed Rhombus.

Code: Select all

#include<iostream>
#include<sstream>
#include<string>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cctype>
#include<set>
#include<bitset>
#include<algorithm>
#include<list>

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<ctype.h>

using namespace std;
//#define print1(a)    cout<<a<<endl
//#define print2(a,b) cout<<a<<" "<<b<<endl
//#define print3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
//#define oo          (1<<30)
#define PI          3.141592653589793
#define pi          2*acos(0)
//#define ERR         1e-5
//#define PRE         1e-8
#define SZ(a)       (int)a.size()
#define LL          long long
#define ISS         istringstream
#define OSS         ostringstream
#define VS          vector<string>
#define VI          vector<int>
#define VD          vector<double>
#define VLL         vector<long long>
#define SII         set<int>::iterator
#define SI          set<int>
#define mem(a,b)    memset(a,b,sizeof(a))
#define fr(i,a,b)   for(i=a;i<=b;i++)
#define frn(i,a,b)  for(i=a;i>=b;i--)

//#define fri(a,b)    for(i=a;i<=b;i++)
//#define frin(a,b)   for(i=a;i>=b;i--)
//#define frj(a,b)    for(j=a;j<=b;j++)
//#define frjn(a,b)   for(j=a;j>=b;j--)
//#define frk(a,b)    for(k=a;k<=b;k++)
//#define frkn(a,b)   for(k=a;k>=b;k--)
//#define frl(a,b)    for(l=a;l<=b;l++)
//#define frln(a,b)   for(l=a;l>=b;l--)

#define EQ(a,b)     (fabs(a-b)<ERR)
#define all(a,b,c)  for(int I=0;I<b;I++)    a[I] = c
#define CROSS(a,b,c,d) ((b.x-a.x)*(d.y-c.y)-(d.x-c.x)*(b.y-a.y))
#define sqr(a)      ((a)*(a))
#define FORE(i,a)   for(typeof((a).begin())i=(a).begin();i!=(a).end();i++)
//#define BE(a)       a.begin(),a.end()
//#define rev(a)      reverse(BE(a));
//#define sorta(a)    sort(BE(a))
#define pb          push_back
#define popb        pop_back
#define round(i,a)  i = ( a < 0 ) ? a - 0.5 : a + 0.5;
#define makeint(n,s)  istringstream(s)>>n
#define countbit(mask) __builtin_popcount(musk)
#define mod         10^9+7


int main()
{
    LL tCase,nCase;
    scanf("%lld",&tCase);
    fr(nCase,1,tCase)
    {
        int co_ordinate[5][3];
        mem(co_ordinate,0);
        scanf("%d %d",&co_ordinate[1][1],&co_ordinate[1][2]);
        scanf("%d %d",&co_ordinate[2][1],&co_ordinate[2][2]);
        scanf("%d %d",&co_ordinate[3][1],&co_ordinate[3][2]);
        scanf("%d %d",&co_ordinate[4][1],&co_ordinate[4][2]);

        int final_pos[5][3];
        mem(final_pos,0);
        int taken[5];
        mem(taken,0);
        int last_pos=1;
        int k,i,j;
        fr(i,1,4)
        {
            fr(k,1,4)
            {

                //printf("taken[%d]=%d\n",k,taken[k]);

                if(taken[k]==0)
                {
                    last_pos=k;
                    //taken[k]=1;
                    final_pos[i][1]=co_ordinate[k][1];
                    final_pos[i][2]=co_ordinate[k][2];
                    k+=5;
                }
            }

            //printf("\nfinal_pos[%d][1]=%d and final_pos[%d][2]=%d\n",i,final_pos[i][1],i,final_pos[i][2]);

            fr(j,1,4)
            {
                    if(final_pos[i][1]>co_ordinate[j][1] && taken[j]==0)
                    {
                        //printf("%d ",j);
                        last_pos=j;
                        final_pos[i][1]=co_ordinate[j][1];
                        final_pos[i][2]=co_ordinate[j][2];
                        //printf("%d.(%d %d)\n",i,final_pos[i][1],final_pos[i][2]);
                    }
                    //else if(final_pos[i][1]==co_ordinate[j][1] && taken[j]==0)
                    //{
                    //    last_pos=j;
                    //    final_pos[i][1]=co_ordinate[j][1];
                    //    final_pos[i][2]=co_ordinate[j][2];
                    //?}
            }


            /*printf("last_pos=%d\n",last_pos);
            printf("final_pos[%d][1]=%d and final_pos[%d][2]=%d\n",i,final_pos[i][1],i,final_pos[i][2]);*/


            taken[last_pos]=1;
            last_pos=0;
        }


        /*fr(i,1,4)
        {
            printf("%d.(%d %d)\n",i,final_pos[i][1],final_pos[i][2]);
        }
        printf("\n");*/


        if(final_pos[1][2]>final_pos[2][2])
        {
            //swap
            swap(final_pos[1][2],final_pos[2][2]);
            swap(final_pos[1][1],final_pos[2][1]);
        }
        if(final_pos[3][2]>final_pos[4][2])
        {
            swap(final_pos[3][2],final_pos[4][2]);
            swap(final_pos[3][1],final_pos[4][1]);
        }

        /*fr(i,1,4)
        {
            printf("%d.(%d %d)\n",i,final_pos[i][1],final_pos[i][2]);
        }*/

        int dx1=abs(final_pos[1][1]-final_pos[3][1]);
        int dx2=abs(final_pos[2][1]-final_pos[4][1]);
        int dy1=abs(final_pos[1][2]-final_pos[2][2]);
        int dy2=abs(final_pos[3][2]-final_pos[4][2]);

        if(dx1==dx2 && dy1==dy2 && dx1==dy1)
        {
            //square or rhombus

            if(final_pos[1][1]==final_pos[2][1]&&final_pos[1][2]==final_pos[3][2])
            {
                //square
                printf("Case %lld: Square",nCase);
            }
            else
            {
                //rhombus
                printf("Case %lld: Rhombus",nCase);

            }
        }
        else if(dx1==dx2 && dy1==dy2 && dx1!=dy1)
        {
            //rectangle or parallelogram
            if(final_pos[1][1]==final_pos[2][1]&&final_pos[1][2]==final_pos[3][2])
            {
                //rectangle
                printf("Case %lld: Rectangle",nCase);
            }
            else
            {
                //parallelogram
                printf("Case %lld: Parallelogram",nCase);
            }
        }
        else if((dy1==dy2 && dx1!=dx2)||(dy1!=dy2 && dx1==dx2))
        {
            //trapezium
            printf("Case %lld: Trapezium",nCase);
        }
        else
        {
            //normal
            printf("Case %lld: Ordinary Quadrilateral",nCase);
        }
        if(nCase!=tCase)
        {
            printf("\n");
        }
    }
    return 0;
}


Re: 11800 - Determine the Shape

Posted: Thu Sep 04, 2014 1:09 am
by brianfry713
Print a newline char at the end of the last line.

Re: 11800 - Determine the Shape

Posted: Thu Sep 11, 2014 11:34 pm
by sabbir_alam_ufo
Still getting WA.
here is the code:

Code: Select all

#include<iostream>
#include<sstream>
#include<string>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cctype>
#include<set>
#include<bitset>
#include<algorithm>
#include<list>

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<ctype.h>

using namespace std;
//#define print1(a)    cout<<a<<endl
//#define print2(a,b) cout<<a<<" "<<b<<endl
//#define print3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
//#define oo          (1<<30)
#define PI          3.141592653589793
#define pi          2*acos(0)
//#define ERR         1e-5
//#define PRE         1e-8
#define SZ(a)       (int)a.size()
#define LL          long long
#define ISS         istringstream
#define OSS         ostringstream
#define VS          vector<string>
#define VI          vector<int>
#define VD          vector<double>
#define VLL         vector<long long>
#define SII         set<int>::iterator
#define SI          set<int>
#define mem(a,b)    memset(a,b,sizeof(a))
#define fr(i,a,b)   for(i=a;i<=b;i++)
#define frn(i,a,b)  for(i=a;i>=b;i--)

//#define fri(a,b)    for(i=a;i<=b;i++)
//#define frin(a,b)   for(i=a;i>=b;i--)
//#define frj(a,b)    for(j=a;j<=b;j++)
//#define frjn(a,b)   for(j=a;j>=b;j--)
//#define frk(a,b)    for(k=a;k<=b;k++)
//#define frkn(a,b)   for(k=a;k>=b;k--)
//#define frl(a,b)    for(l=a;l<=b;l++)
//#define frln(a,b)   for(l=a;l>=b;l--)

#define EQ(a,b)     (fabs(a-b)<ERR)
#define all(a,b,c)  for(int I=0;I<b;I++)    a[I] = c
#define CROSS(a,b,c,d) ((b.x-a.x)*(d.y-c.y)-(d.x-c.x)*(b.y-a.y))
#define sqr(a)      ((a)*(a))
#define FORE(i,a)   for(typeof((a).begin())i=(a).begin();i!=(a).end();i++)
//#define BE(a)       a.begin(),a.end()
//#define rev(a)      reverse(BE(a));
//#define sorta(a)    sort(BE(a))
#define pb          push_back
#define popb        pop_back
#define round(i,a)  i = ( a < 0 ) ? a - 0.5 : a + 0.5;
#define makeint(n,s)  istringstream(s)>>n
#define countbit(mask) __builtin_popcount(musk)
#define mod         10^9+7


int main()
{
    LL tCase,nCase;
    scanf("%lld",&tCase);
    fr(nCase,1,tCase)
    {
        int co_ordinate[5][3];
        mem(co_ordinate,0);
        scanf("%d %d",&co_ordinate[1][1],&co_ordinate[1][2]);
        scanf("%d %d",&co_ordinate[2][1],&co_ordinate[2][2]);
        scanf("%d %d",&co_ordinate[3][1],&co_ordinate[3][2]);
        scanf("%d %d",&co_ordinate[4][1],&co_ordinate[4][2]);

        int final_pos[5][3];
        mem(final_pos,0);
        int taken[5];
        mem(taken,0);
        int last_pos=1;
        int k,i,j;
        fr(i,1,4)
        {
            fr(k,1,4)
            {

                //printf("taken[%d]=%d\n",k,taken[k]);

                if(taken[k]==0)
                {
                    last_pos=k;
                    //taken[k]=1;
                    final_pos[i][1]=co_ordinate[k][1];
                    final_pos[i][2]=co_ordinate[k][2];
                    k+=5;
                }
            }

            //printf("\nfinal_pos[%d][1]=%d and final_pos[%d][2]=%d\n",i,final_pos[i][1],i,final_pos[i][2]);

            fr(j,1,4)
            {
                    if(final_pos[i][1]>co_ordinate[j][1] && taken[j]==0)
                    {
                        //printf("%d ",j);
                        last_pos=j;
                        final_pos[i][1]=co_ordinate[j][1];
                        final_pos[i][2]=co_ordinate[j][2];
                        //printf("%d.(%d %d)\n",i,final_pos[i][1],final_pos[i][2]);
                    }
                    //else if(final_pos[i][1]==co_ordinate[j][1] && taken[j]==0)
                    //{
                    //    last_pos=j;
                    //    final_pos[i][1]=co_ordinate[j][1];
                    //    final_pos[i][2]=co_ordinate[j][2];
                    //?}
            }


            /*printf("last_pos=%d\n",last_pos);
            printf("final_pos[%d][1]=%d and final_pos[%d][2]=%d\n",i,final_pos[i][1],i,final_pos[i][2]);*/


            taken[last_pos]=1;
            last_pos=0;
        }


        /*fr(i,1,4)
        {
            printf("%d.(%d %d)\n",i,final_pos[i][1],final_pos[i][2]);
        }
        printf("\n");*/


        if(final_pos[1][2]>final_pos[2][2])
        {
            //swap
            swap(final_pos[1][2],final_pos[2][2]);
            swap(final_pos[1][1],final_pos[2][1]);
        }
        if(final_pos[3][2]>final_pos[4][2])
        {
            swap(final_pos[3][2],final_pos[4][2]);
            swap(final_pos[3][1],final_pos[4][1]);
        }

        /*fr(i,1,4)
        {
            printf("%d.(%d %d)\n",i,final_pos[i][1],final_pos[i][2]);
        }*/

        int dx1=abs(final_pos[1][1]-final_pos[3][1]);
        int dx2=abs(final_pos[2][1]-final_pos[4][1]);
        int dy1=abs(final_pos[1][2]-final_pos[2][2]);
        int dy2=abs(final_pos[3][2]-final_pos[4][2]);

        if(dx1==dx2 && dy1==dy2 && dx1==dy1)
        {
            //square or rhombus

            if(final_pos[1][1]==final_pos[2][1]&&final_pos[1][2]==final_pos[3][2])
            {
                //square
                printf("Case %lld: Square",nCase);
            }
            else
            {
                //rhombus
                printf("Case %lld: Rhombus",nCase);

            }
        }
        else if(dx1==dx2 && dy1==dy2 && dx1!=dy1)
        {
            //rectangle or parallelogram
            if(final_pos[1][1]==final_pos[2][1]&&final_pos[1][2]==final_pos[3][2])
            {
                //rectangle
                printf("Case %lld: Rectangle",nCase);
            }
            else
            {
                //parallelogram
                printf("Case %lld: Parallelogram",nCase);
            }
        }
        else if((dy1==dy2 && dx1!=dx2)||(dy1!=dy2 && dx1==dx2))
        {
            //trapezium
            printf("Case %lld: Trapezium",nCase);
        }
        else
        {
            //normal
            printf("Case %lld: Ordinary Quadrilateral",nCase);
        }
        printf("\n");
    }
    return 0;
}

Re: 11800 - Determine the Shape

Posted: Fri Sep 12, 2014 10:47 pm
by brianfry713
Try running your code on the sample input.

Re: 11800 - Determine the Shape

Posted: Tue Sep 16, 2014 9:41 pm
by sabbir_alam_ufo
Thanks I got the point.

Re: 11800 - Determine the Shape

Posted: Sun Dec 07, 2014 2:49 pm
by lighted
jurajz wrote: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 :D
Thanks, finally got Accepted, this was reason of many WA's.

Re: 11800 - Determine the Shape

Posted: Sat Dec 13, 2014 12:56 am
by stronk111
My code passed all forum tests but I'm still getting WA. Can you check my code?
I'm using cross product to determine parallelism and dot product to determine perpendicularity. I defined int as long long to avoid mistakes.

Code: Select all

removed

Re: 11800 - Determine the Shape

Posted: Sat Dec 13, 2014 4:08 pm
by lighted
Input

Code: Select all

1
2 1
0 0
2 -2
1 2
Acc Output

Code: Select all

Case 1: Trapezium

Re: 11800 - Determine the Shape

Posted: Sat Dec 13, 2014 6:04 pm
by stronk111
Thank you. I made a mistake in comparison function.

Re: 11800 - Determine the Shape

Posted: Thu Dec 18, 2014 6:29 pm
by Shahidul.CSE

Code: Select all

Accepted

Re: 11800 - Determine The Shape

Posted: Fri Dec 19, 2014 12:41 am
by brianfry713
brianfry713 wrote:Try solving it without using floating point.

Re: 11800 - Determine the Shape

Posted: Fri Dec 19, 2014 4:56 am
by Shahidul.CSE

Code: Select all

Ac

Re: 11800 - Determine the Shape

Posted: Sat Dec 20, 2014 3:30 am
by brianfry713
stronk111 wrote:I'm using cross product to determine parallelism and dot product to determine perpendicularity.
There are other ways to solve it than computing angles, avoid floating point when possible.
http://floating-point-gui.de/

Re: 11800 - Determine the Shape

Posted: Sat Jan 31, 2015 12:19 am
by Tarango_Flash7
Can anyone help me!I can't find out what's wrong in my code.It passes all the test cases i checked but getting WA in UVa :(

Code: Select all

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stdio.h>
#include <cmath>
#define Pi 3.14159265359
#define EPS 1e-9
using namespace std;
int A,B,C,D;

struct Pnt{
    int x;
    int y;
}Point[4];

bool acompare(Pnt lhs, Pnt rhs){
     return lhs.y > rhs.y;
 }

void setPoint2(){
    sort(Point,Point+4,acompare);
    if(Point[0].x<Point[1].x){
        A = 0;B = 1;
    }else{
        B = 0;A = 1;
    }
    if(Point[2].x<Point[3].x){
        D = 2;C = 3;
    }else{
        D = 3;C = 2;
    }
}

int isEqual(){
    if(Point[A].x == Point[B].x && Point[A].y == Point[B].y) return 1;
    if(Point[A].x == Point[C].x && Point[A].y == Point[C].y) return 1;
    if(Point[A].x == Point[D].x && Point[A].y == Point[D].y) return 1;
    if(Point[B].x == Point[C].x && Point[B].y == Point[C].y) return 1;
    if(Point[B].x == Point[D].x && Point[B].y == Point[D].y) return 1;
    if(Point[C].x == Point[D].x && Point[C].y == Point[D].y) return 1;
    return 0;
}

int main(){
    int nCase;
    scanf("%d",&nCase);
    for(int cs = 1;cs<=nCase;cs++){
        for(int i = 0;i<4;i++){
            scanf("%d %d",&Point[i].x,&Point[i].y);
        }
        setPoint2();
        double AB = abs((double)sqrt((Point[A].x-Point[B].x)*(Point[A].x-Point[B].x) + (Point[A].y-Point[B].y)*(Point[A].y-Point[B].y)));
        double AC = abs((double)sqrt((Point[A].x-Point[C].x)*(Point[A].x-Point[C].x) + (Point[A].y-Point[C].y)*(Point[A].y-Point[C].y)));
        double AD = abs((double)sqrt((Point[A].x-Point[D].x)*(Point[A].x-Point[D].x) + (Point[A].y-Point[D].y)*(Point[A].y-Point[D].y)));
        double BC = abs((double)sqrt((Point[C].x-Point[B].x)*(Point[C].x-Point[B].x) + (Point[C].y-Point[B].y)*(Point[C].y-Point[B].y)));
        double CD = abs((double)sqrt((Point[C].x-Point[D].x)*(Point[C].x-Point[D].x) + (Point[C].y-Point[D].y)*(Point[C].y-Point[D].y)));
        double BD = abs((double)sqrt((Point[B].x-Point[D].x)*(Point[B].x-Point[D].x) + (Point[B].y-Point[D].y)*(Point[B].y-Point[D].y)));

        if((abs(AB - BC) < EPS) && (abs(BC - CD) < EPS) && (abs(CD - AB) < EPS)){
            if(abs(AC - BD) < EPS){
                printf("Case %d: Square\n",cs);
            }else{
                printf("Case %d: Rhombus\n",cs);
            }
        }else if((abs(AB - CD) < EPS) && (abs(BC - AD )< EPS)){
            if(abs(AC - BD) < EPS){
                printf("Case %d: Rectangle\n",cs);
            }else{
                printf("Case %d: Parallelogram\n",cs);
            }
        }else{
            //double slopeAB = (double)(Point[B].y - Point[A].y)/(Point[B].x - Point[A].x);
            //double slopeDC = (double)(Point[C].y - Point[D].y)/(Point[C].x - Point[D].x);
            //double slopeAD = (double)(Point[D].y - Point[A].y)/(Point[D].x - Point[A].x);
            //double slopeBC = (double)(Point[C].y - Point[B].y)/(Point[C].x - Point[B].x);
            double slopeABDC = (double)(Point[B].y - Point[A].y)*(Point[C].x - Point[D].x) - (double)(Point[B].x - Point[A].x)*(Point[C].y - Point[D].y);
            double slopeADBC = (double)(Point[D].y - Point[A].y)*(Point[C].x - Point[B].x) - (double)(Point[D].x - Point[A].x)*(Point[C].y - Point[B].y);
            slopeABDC = abs(slopeABDC);
            slopeADBC = abs(slopeADBC);
            if(slopeABDC <EPS || slopeADBC <EPS){
                if(abs(AB-BC)>EPS && abs(AB-AD)>EPS && abs(AB-CD)>EPS && abs(BC-AB)>EPS && abs(BC-CD)>EPS && abs(CD-AD)>EPS)
                    printf("Case %d: Trapezium\n",cs);
                else
                    printf("Case %d: Ordinary Quadrilateral\n",cs);
            }else{
                printf("Case %d: Ordinary Quadrilateral\n",cs);
            }
        }
    }
}

Re: 11800 - Determine The Shape

Posted: Mon Feb 02, 2015 11:44 pm
by brianfry713
brianfry713 wrote:
brianfry713 wrote:Try solving it without using floating point.