OJ Board

Posted: **Mon Oct 02, 2006 3:38 am**

how this problem can be solved?

Posted: **Mon Oct 02, 2006 4:24 am**

sorting

Posted: **Mon Oct 02, 2006 4:25 am**

I think this is a beautiful problem. I liked it very much. A point is part of exactly one vertical and one horizontal edge. Suppose the first point is (x,y). Try to find out two points (x,w) and (z,y). And continue searching until no point is left. To find these two points you have to maintain a strategy.

I m giving a test case. Draw it on a paper and try to find a strategy to build the polygon.

Input:

Code: Select all

Output:

Code: Select all

Hope it helps.

Posted: **Mon Oct 02, 2006 1:39 pm**

there r duplicate points in the input too..

how to handle them ....

i printed -1 for that but gat WA...

i then erased them form the list then too wa...

don't know what to do

Posted: **Mon Oct 02, 2006 1:41 pm**

btw is my observation right that if no. of "distinct" points is odd then no rectilinear polygon is possible ...
if not whats the counter example...

Posted: **Mon Oct 02, 2006 2:33 pm**

The problem states...

each vertex is an endpoint of exactly one horizontal edge and one vertical edge

And the edges are vertical or horizontal. So, we need even number of points.

Posted: **Mon Oct 02, 2006 3:19 pm**

yeah thats what I meant...

wat about my second n more imporatant question??

there are duplicate points in the input ...

hoe to handle those???

Posted: **Mon Oct 02, 2006 3:28 pm**

There must be something wrong with your program, because there are _no_ duplicate points in the input.

Posted: **Mon Oct 02, 2006 3:58 pm**

my algo is something like this:

1) get two sorted lists , one by X and other by Y coordinates...
2) in each list check whether we can forms pairs ... by pair i mean same
coordinate value by which the list is sorted.. if not -1

3) else we have an answer which is the sum of the other co-ordinates of the pairs ...

am i right???

Posted: **Mon Oct 02, 2006 4:02 pm**

here is my code...
I assure i will remove it as soon as i get the flaw in it..

Code: Select all

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include <functional>      // For greater<int>( )
#include<cassert>

using namespace std;
struct node{
        int x;
        int y;
        //int num;
};    
 
bool UDgreater(node a,node b){
    if(a.x==b.x) 
            return a.y<b.y;
        
    return a.x<b.x;
} 

bool UDgreater1(node a,node b){
    if(a.y==b.y)
        return a.x<b.x;
         
    return a.y<b.y;
}   


int main(){
   
    int cases,nn;
    scanf("%d",&cases);
    
    while(cases--){

            scanf("%d",&nn);
            vector<node> v;
            node n;
            
            //input points
            for(int i=0;i<nn;i++){
                
                scanf("%d%d",&n.x,&n.y);
                v.push_back(n);
            }    
          
            // horizonal and vertical lists...
            vector<node > H=v;
            
            sort(v.begin(),v.end(),UDgreater);
            sort(H.begin(),H.end(),UDgreater1);
            
            f=false;
            int ret=0;
            for(int i=0;i<nn-1;i+=2){
                
                //pair not found..
                if(v[i].x!=v[i+1].x){
                    printf("-1\n");
                    f=true;
                    break;
                }
                // pair found add y coordinate
                ret+=abs(v[i+1].y-v[i].y);
                
                // pair not found..
                if(H[i].y!=H[i+1].y){
                    printf("-1\n");
                    f=true;
                    break;
                }       
                // pair found add x coordinate
                ret+=abs(H[i+1].x-H[i].x); 
            }    
            if(f) continue;
                        
            printf("%i\n",ret);
            
     }
     return 0;
}

Posted: **Mon Oct 02, 2006 4:50 pm**

can any one tell me what is wrong with my code ? thanks in advance

Code: Select all

removed

Posted: **Mon Oct 02, 2006 5:18 pm**

the idea is same with your code too...

so whats wrong with me , is wrong with u....

btw i checked for duplicate points using assert function n it gave runtime error.. doesn't it mean that there r duplicate points?

Posted: **Mon Oct 02, 2006 6:04 pm**

vinay wrote:the idea is same with your code too...

so whats wrong with me , is wrong with u....

btw i checked for duplicate points using assert function n it gave runtime error.. doesn't it mean that there r duplicate points?

Well, I also checked with assert, and my code runs fine.

About your code: it will not compile, because the variable f is not declared.
Try this input:

Code: Select all

The answer should not be 16.

Posted: **Mon Oct 02, 2006 6:16 pm**

that means my algo is wrong....

so do i need to simulate the process of choosing a horizontal path and then a vwrticale path alternately....

or there is other way possible , ie without simulation...

Posted: **Mon Oct 02, 2006 6:43 pm**

No, your method is correct, but you just need one additional step.

OJ Board

11106 - Rectilinear Polygon

11106 - Rectilinear Polygon