Page 3 of 4

### Re: 11800 - Determine the Shape

Posted: Fri Aug 29, 2014 10:42 pm
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;
}

### Re: 11800 - Determine the Shape

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

### Re: 11800 - Determine the Shape

Posted: Thu Sep 11, 2014 11:34 pm
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;
}

### Re: 11800 - Determine the Shape

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

### Re: 11800 - Determine the Shape

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

### Re: 11800 - Determine the Shape

Posted: Sun Dec 07, 2014 2:49 pm
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

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.

### Re: 11800 - Determine the Shape

Posted: Sat Dec 13, 2014 12:56 am
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
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
Thank you. I made a mistake in comparison function.

### Re: 11800 - Determine the Shape

Posted: Thu Dec 18, 2014 6:29 pm

Code: Select all

Accepted

### Re: 11800 - Determine The Shape

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

### Re: 11800 - Determine the Shape

Posted: Fri Dec 19, 2014 4:56 am

Code: Select all

Ac

### Re: 11800 - Determine the Shape

Posted: Sat Dec 20, 2014 3:30 am
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
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