## 11800 - Determine the Shape

Moderator: Board moderators

sabbir_alam_ufo
New poster
Posts: 16
Joined: Fri Nov 15, 2013 9:33 pm

### Re: 11800 - Determine the Shape

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 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
}
if(nCase!=tCase)
{
printf("\n");
}
}
return 0;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11800 - Determine the Shape

Print a newline char at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

sabbir_alam_ufo
New poster
Posts: 16
Joined: Fri Nov 15, 2013 9:33 pm

### Re: 11800 - Determine the Shape

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 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("\n");
}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11800 - Determine the Shape

Try running your code on the sample input.
Check input and AC output for thousands of problems on uDebug!

sabbir_alam_ufo
New poster
Posts: 16
Joined: Fri Nov 15, 2013 9:33 pm

### Re: 11800 - Determine the Shape

Thanks I got the point.

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 11800 - Determine the Shape

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
Thanks, finally got Accepted, this was reason of many WA's.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

stronk111
New poster
Posts: 4
Joined: Tue Nov 11, 2014 3:20 am

### Re: 11800 - Determine the Shape

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
``````
Last edited by stronk111 on Sat Dec 13, 2014 6:03 pm, edited 1 time in total.

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 11800 - Determine the Shape

Input

Code: Select all

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

Code: Select all

``````Case 1: Trapezium
``````
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

stronk111
New poster
Posts: 4
Joined: Tue Nov 11, 2014 3:20 am

### Re: 11800 - Determine the Shape

Thank you. I made a mistake in comparison function.

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am

### Re: 11800 - Determine the Shape

Code: Select all

``Accepted``
Last edited by Shahidul.CSE on Tue Dec 23, 2014 8:20 pm, edited 1 time in total.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
Email me: shahidul.cse.brur@gmail.com

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11800 - Determine The Shape

brianfry713 wrote:Try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am

### Re: 11800 - Determine the Shape

Code: Select all

``Ac``
Last edited by Shahidul.CSE on Tue Dec 23, 2014 8:20 pm, edited 1 time in total.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
Email me: shahidul.cse.brur@gmail.com

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11800 - Determine the Shape

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/
Check input and AC output for thousands of problems on uDebug!

Tarango_Flash7
New poster
Posts: 5
Joined: Mon Jan 26, 2015 1:31 am

### Re: 11800 - Determine the Shape

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);
printf("Case %d: Trapezium\n",cs);
else
}else{
}
}
}
}``````
Last edited by brianfry713 on Mon Feb 02, 2015 11:44 pm, edited 1 time in total.