CareerCup

One idea, not sure whether this is correct.

Construct two graphs, one for x-coordinate--Gx, one for y-coordinate--Gy.

For Gx, If x1 < x2, then we have an edge from x1->x2, if x1 > x2, one edge x1<-x2. If x1 == x2, combine x1 and x2 together.

Similarly for Gy.

In the end, we check whether there exists a cycle in Gx or Gy. If this is true, then the answer is impossible.

For example, p1 SE p2, we have x1 > x2 and y1 < y2.
Gx: x1 <-- x2 Gy: y1 -->y2

p2 SE p3, we have x2 > x3 and y2 < y3.
Gx: x1 <-- x2 <-- x3 Gy: y1 -->y2 -->y3

p3 SE p1, we have x3 > x1 and y3 < y1
In Gx, we have a cycle from x1 <-- x2 <-- x3 <-- x1. So it is impossible.


Any comment/correction/improvement is welcome...

quick solution in python

#Given the relative positions (S, W, N, E, SW, NW, SE, NE) of some pairs of points on a 2D plane, 
#determine whether it is possible. No two points have the same coordinates. 

# INPUT
# p12is SouthEast of p1
c1 = ("p1","p2","SE")
# p3 is SouthEast of p2
c2 = ("p2","p3","SE")
# p1 is SouthEast of p3
c3 = ("p3","p1","SE")
cs = [c1,c2,c3]

# Mappings
translations = {
	"S":{"S"},
	"W":{"W"},
	"N":{"N"},
	"E":{"E"},
	"SW":{"S","W"},
	"SE":{"S","E"},
	"NW":{"N","W"},
	"NE":{"N","E"},
}

opposites = {
	"S":"N",
	"W":"E",
	"N":"S",
	"E":"W"
}



# returns true if isuch nformation regarding the direction exists
def isInDirection(src,dst,graph,dr):
	if dst in graph[src][dr]:
		return True
	for meta_dst in graph[src][dr]:
		if isInDirection(meta_dst,dst,graph,dr):
			return True
	return False


emptyNode = lambda : {"S":[],"W":[],"N":[],"E":[]}

graph = {}
for c in cs:
	src,dst,directions = c[0],c[1],c[2]
	if not(src in graph):
		graph[src] = emptyNode()
	if not(dst in graph):
		graph[dst] = emptyNode()
	# c0 is c2 of c1
	for direction in translations[directions]:
		if isInDirection(src,dst,graph,opposites[direction]):
			print "Impossible for " + dst + " to be " + directions + " of " + src +\
			 " because " + dst  + " is " + opposites[direction] + " of it"
			break
		graph[src][direction].append(dst)
		graph[dst][opposites[direction]].append(src)
#print graph

{{ if we have input p1 SE p2, p2 SE p3, p3 SE p4, p4 NW p5 and p5 SE p1, output depends upon p5, if p5 > p1 - this path invalid.
if p1 < p5 this path is valid

How we identify weather p5 > p1? }}

For each x and y, fill two matrices. We only want one triangle so it can be optimized into one.
size of matrix side is the amount of points. Enter only what is given. If p1 and p2 p1.x > p2.x enter 1 at position 1,2. less, enter -1. equal 0.

For every filled point, see that if all filled elements on the same row and column >= 1 and current is -1: impossible. Similarly, all are <= 1 and current one 1: impossible

Ithink this question maybe can be sloved with bit manipulation.

import java.util.*;
class RelativePositioning {
	
	Set<String> getValue(String key, HashMap<String, Set<String>> hashMap) {
		Set<String> value = hashMap.get(key);
		if(value == null) {
			value = new HashSet<String>();
		}
		return value;
	}
	
	boolean isValueRepeated(String key, ArrayList<String> keyList, HashSet<String> visitedKeys, HashMap<String, Set<String>> hashMap) {
		if(visitedKeys.contains(key)) return false;
		keyList.add(key);
		Set<String> valuesSet = hashMap.get(key);
		for(String value : valuesSet) {
			if(keyList.contains(value)) return true;
			@SuppressWarnings("unchecked")
			ArrayList<String> keyListClone = (ArrayList<String>)keyList.clone();
			if(isValueRepeated(value, keyListClone, visitedKeys, hashMap)) return true;
		}
		visitedKeys.add(key);
		return false;
	}
	
	boolean checkForLoops(HashMap<String, Set<String>> hashMap) {
		Set<String> keys = hashMap.keySet();
		HashSet<String> visitedKeys = new HashSet<String>();
		for(String key: keys) {
			ArrayList<String> keyList = new ArrayList<String>();
			if(isValueRepeated(key, keyList, visitedKeys, hashMap)) return true;
		}
		return false;
	}
	
	boolean fitInAGraph(String[] positions) {
		HashMap<String, Set<String>> xHashMap = new HashMap<String, Set<String>>();
		HashMap<String, Set<String>> yHashMap = new HashMap<String, Set<String>>();
		for(String position: positions) {
			String[] positionParts = position.split(" ");
			String val1 = positionParts[0];
			String val2 = positionParts[2];
			String relation = positionParts[1];
			
			Set<String> val1ArrayX = getValue(val1, xHashMap);
			Set<String> val2ArrayX = getValue(val2, xHashMap);
			Set<String> val1ArrayY = getValue(val1, yHashMap);
			Set<String> val2ArrayY = getValue(val2, yHashMap);
			
			if(relation.equals("S")) {
				val1ArrayX.addAll(val2ArrayX);
				val2ArrayX = val1ArrayX;
				val2ArrayY.add(val1);
			} else if(relation.equals("W")) {
				val1ArrayY.addAll(val2ArrayY);
				val2ArrayY = val1ArrayY;
				val2ArrayX.add(val1);
			} else if(relation.equals("N")) {
				val1ArrayX.addAll(val2ArrayX);
				val2ArrayX = val1ArrayX;
				val1ArrayY.add(val2);
			} else if(relation.equals("E")) {
				val1ArrayY.addAll(val2ArrayY);
				val2ArrayY = val1ArrayY;
				val1ArrayX.add(val2);
			} else if(relation.equals("SW")) {
				val2ArrayX.add(val1);
				val2ArrayY.add(val1);
			} else if(relation.equals("NW")) {
				val1ArrayY.add(val2);
				val2ArrayX.add(val1);
			} else if(relation.equals("SE")) {
				val2ArrayY.add(val1);
				val1ArrayX.add(val2);
			} else if(relation.equals("NE")) {
				val1ArrayX.add(val2);
				val1ArrayY.add(val2);
			}
			xHashMap.put(val1, val1ArrayX);
			xHashMap.put(val2, val2ArrayX);
			yHashMap.put(val1, val1ArrayY);
			yHashMap.put(val2, val2ArrayY);
			
		}
		return !checkForLoops(xHashMap) && !checkForLoops(yHashMap);
	}

	public static void  main(String[] inputs) {
		RelativePositioning rp = new RelativePositioning();
		String[] positions = new String[10];
		positions[0] = "p1 N p3";
		positions[1] = "p1 NW p5";
		positions[2] = "p1 NW p2";
		positions[3] = "p2 SW p6";
		positions[4] = "p4 SW p6";
		positions[5] = "p3 W p2";
		positions[6] = "p4 S p1";
		positions[7] = "p5 E p4";
		positions[8] = "p1 W p6";
		positions[9] = "p6 NE p5";
		System.out.println(rp.fitInAGraph(positions));
		/*above test: 
		  ________________
		  | p1 |    | p6 |
		  _________________
		  | p3 | p2 |    |
		  ________________
		  | p4 | p5 |    |
		  ________________
		*/
		
	}
}

public void solve(String input) {
  HashMap<String, Point> coordinates = new HashMap<>();
  String[] pairs = input.split(",");
  for (String pair : pairs) {
    String[] token = pair.split("\\s+");
    if (!coordinates.contains(token[0])) {
      coordinates.add(token[0], new Point(0, 0));
    }
    Point p1 = coordinates.get(token[0]);
    Point p2 = null;
    if (token[1].equals("S")) {
    p2 = new Point(token[2], new Point(p1.x, p1.y - 1)); 
    } else if (token[1].equals("W")) {
    p2 = new Point(token[2], new Point(p1.x - 1, p1.y));    
    } else if (token[1].equals("N")) {
    p2 = new Point(token[2], new Point(p1.x, p1.y + 1));    
    } else if (token[1].equals("E")) {
    p2 = new Point(token[2], new Point(p1.x + 1, p1.y));    
    } else if (token[1].equals("SW")) {
    p2 = new Point(token[2], new Point(p1.x - 1, p1.y - 1));    
    } else if (token[1].equals("NW")) {
    p2 = new Point(token[2], new Point(p1.x - 1, p1.y + 1));    
    } else if (token[1].equals("SE")) {
    p2 = new Point(token[2], new Point(p1.x + 1, p1.y - 1));    
    } else if (token[1].equals("NE")) {
    p2 = new Point(token[2], new Point(p1.x + 1, p1.y + 1));    
    }
    if (coordinates.contains(token[2]) && p2 != null) {
      if (!p2.equals(coordinates.get(p2))) {
        System.out.println("Impossible");
      }
    }
  }
}

#include <iostream>
#include <assert.h>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>

using namespace std;

typedef struct
{
	string src;
	string dst;
	string angle;
}Relation;

typedef struct RelationNode_{
	string name;
	map<string, set<RelationNode_*> > nodes;
}RelationNode;

RelationNode *findNodeByName(RelationNode * root, const string& name, const string& angle)
{
	queue<RelationNode *> task;
	task.push(root);
	while (!task.empty())
	{
		if (task.front()->name == name)
			return task.front();

		for ( const auto& node : task.front()->nodes )
			if (angle.empty() || node.first == angle)
				for ( const auto& nodeInSet : node.second )
				task.push(nodeInSet);

		task.pop();
	}

	return nullptr;
}

string getOpposite(const string& angle)
{
		 if ("S" == angle) return "N";  else if ("N" == angle)  return "S";
	else if ("W" == angle) return "E";  else if ("E" == angle)  return "W";

	else if ("NE" == angle) return "SW";  else if ("SW" == angle)  return "NE";
	else if ("NW" == angle) return "SE";  else if ("SE" == angle)  return "NW";

	assert(false);
	return string();
}

bool TryAddNode(RelationNode **root, const Relation& relation)
{
	if (!*root)
	{
		*root = new RelationNode();
		(*root)->name = relation.src;
	}

	const auto srcNode = findNodeByName(*root, relation.src, string());
	if ( !srcNode )
		// Sorry, for this task we do not create flat hierarchy. Only root-based
		// It is easy to extend it by vector of roots.
		return false;

	const auto dstNode = findNodeByName(*root, relation.dst, string());
	if ( dstNode )
		// If we have this node already, we just make sure that is is correctly placed and test way back
		return 	findNodeByName(srcNode, relation.dst, relation.angle) 
				|| 
				findNodeByName(dstNode, relation.src, getOpposite(relation.angle));

	const auto dst = new RelationNode();
	dst->name = relation.dst;

	if ( srcNode->nodes.end() == srcNode->nodes.find(relation.angle))
	{
		auto iter = srcNode->nodes.insert(make_pair(relation.angle, set<RelationNode_*>()));
		iter.first->second.insert(dst);
	}
	else
	{
		srcNode->nodes[relation.angle].insert(dst);
	}

	return true;
}

bool isPossible(const vector<Relation>& pairs)
{
	if (pairs.empty())
		return true;

	RelationNode *root = nullptr;
	for (const auto& relation : pairs)
	{
		if (!TryAddNode(&root, relation))
			return false;
	}

	return true;
}

void Google4()
{
	Relation r1 { "p1", "p2", "SE" };
	Relation r2 { "p2", "p3", "SE" };
	Relation r3 { "p3", "p1", "SE" };
	Relation r4 { "p3", "p1", "NW" };

	assert( true == isPossible({ r1, r2 }) );
	assert( false == isPossible({ r1, r2, r3 }) );
	assert( true == isPossible({ r1, r2, r4 }) );
}

class Program
    {
        static void Main(string[] args)
        {
            string test = "p1 SE p2, p2 SE p3, p3 SE p1";
            ThreePoints tp = new ThreePoints(test);
            bool poss = tp.CheckPossible();
            Console.WriteLine("Possible? " + poss);
        }
    }

    public class ThreePoints
    {//Idea: to solve this problem, we assume two points do have the same coordinates and do the evaluation. 
     //These two points all have (0,0) coordinate.Because all points are in relative position, this is fine.
     //Now we only need to enumerate all possible locations for the third point, I call it nonzeropoint. Array nonzeropoints have all values for it.
     //If there is no valid evaluation in any possible value combination of the three points. we output "impossible"
        List<Conditon> conditions = new List<Conditon>();
        Dictionary<string, Point> pointmap = new Dictionary<string, Point>();
        Point[] nonzeropoints = new Point[]{
            new Point(0,1),new Point(0,-1),
            new Point(1,0),new Point(-1,0),
            new Point(1,1),new Point(-1,-1),
            new Point(-1,1),new Point(1,-1),
        };
        public class Point
        {
            public int x;
            public int y;
            public Point(int x, int y){
                this.x=x;
                this.y=y;
            }
        }

        public class Conditon
        {
            public string keyA;
            public string keyB;
            public string Operator;
        }
        public ThreePoints(string formula)
        {
            string[] phrases = formula.Split(',');

            foreach (string phrase in phrases)
            {
                string[] words = phrase.Trim().Split(' ');
                Conditon acondition = new Conditon();
                if (!pointmap.ContainsKey(words[0]))
                {
                    Point apoint = new Point(0,0);
                    pointmap.Add(words[0], apoint);
                }
                acondition.keyA = words[0];
                acondition.Operator = words[1];
                if (!pointmap.ContainsKey(words[2]))
                {
                    Point apoint = new Point(0,0);
                    pointmap.Add(words[2], apoint);
                }
                acondition.keyB = words[2];
                conditions.Add(acondition);
            }
        }

        public bool CheckPossible()
        {
            string[] keys = pointmap.Keys.ToArray();
            foreach (string key in keys)
            {
                if (CheckOneCombination(key))
                {
                    return true;
                }
            }
            return false;
        }

        private bool CheckOneCombination(string NonZeroPoint)
        {
            //non zero point coordinates have the following values:
            // (0,1),(1,1),(1,0), (0,-1), (-1,0),(-1,-1), (1,-1), (-1,1)
            foreach(Point nzpoint in nonzeropoints){
                string[] keys = pointmap.Keys.ToArray();
                foreach (string key in keys)
                {
                    if (key.Equals(NonZeroPoint))
                    {
                        pointmap[key] = nzpoint;
                    }
                    else
                    {
                        pointmap[key]= new Point(0,0);
                    }
                }
                bool conResult = true;
                foreach(Conditon con in conditions){
                    if (!Evaluate(con))
                    {
                        conResult = false;
                        break;
                    }
                }
                if (conResult)
                {
                    return true;
                }
            }
            return false;
        }
        /// <summary>
        /// Evaluate Point A Operator Point B
        /// </summary>
        /// <param name="a"></param>
        /// <param name="op">N, S, W, E and a combination like NW, NE, SW, SE</param>
        /// <param name="b"></param>
        /// <returns></returns>
        private bool Evaluate(Conditon con)
        {

            Point a = pointmap[con.keyA];
            string op = con.Operator;
            Point b = pointmap[con.keyB];
            if (op.Contains("S")) //point b is on S of point a
            {
                if(a.y <= b.y) return false;
            }
            else if (op.Contains("N")) //point b is on N of point a
            {
                if (a.y >= b.y) return false;
            }
            if (op.Contains("E")) //point b is on E of point a
            {
                if (a.x >= b.x) return false;
            }
            else if (op.Contains("W")) //point b is on W of point a
            {
                if (a.x <= b.x) return false;
            }
            return true;
        }
    }

@wws 's idea is intreasting, I just not sure how to merge two nodes. Disjoint set may be a way, we can merge the neighbors of two nodes to their fathors, but other nodes may also point to two nodes who share their father, and I can fingure out an efficient way to merge this condition.
The nearest distance between two nodes cross my mind. If we define a directed graph like this: if x1<x2, then the distance d[x2][x1] = -1, if x1 == x2, d[x1][x2] = d[x2][x1] == 0, y is the same. I use floyd-warshall to get the distance between any two nodes and if there are a circle, the distance of d[i][i] will definite be negative.
I use test cases from @Adi, here is my implementation. Any comment/correction is welcome!

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <sstream>
using namespace std;

const int MAX_V = 102;
const int INF = 100000;

int d[2][MAX_V][MAX_V];

map<string, int> dict;
int mid;
int getId(string &s){
    if(dict.find(s) == dict.end()){
        dict[s] = mid++;
    }
    return dict[s];
}

void handle_input(int a, int b, string &op){
    if(op == "S"){
        d[0][a][b] = d[0][b][a] = 0;
        d[1][b][a] = -1;
    }else if(op == "W"){
        d[1][a][b] = d[1][b][a] = 0;
        d[0][b][a] = -1;
    }else if(op == "N"){
        d[0][a][b] = d[0][b][a] = 0;
        d[1][a][b] = -1;
    }else if(op == "E"){
        d[1][a][b] = d[1][b][a] = 0;
        d[0][a][b] = -1;
    }else if(op == "SW"){
        d[0][b][a] = -1;
        d[1][b][a] = -1;
    }else if(op == "NW"){
        d[0][b][a] = -1;
        d[1][a][b] = -1;
    }else if(op == "SE"){
        d[0][a][b] = -1;
        d[1][b][a] = -1;
    }else if(op == "NE"){
        d[0][a][b] = -1;
        d[1][a][b] = -1;
    }
}

bool floyd_warshall(int G[MAX_V][MAX_V]){ 
    for(int k=0;k<mid;++k)
        for(int i=0;i<mid;++i)
            for(int j=0;j<mid;++j){
                G[i][j] = min(G[i][j], G[i][k]+G[k][j]);
            }
    for(int i=0;i<mid;++i){
        if(G[i][i]<0)   return false;
    }
    return true;
}

void init(){
    for(int i=0;i<MAX_V;++i)  for(int j=0;j<MAX_V;++j){
        d[0][i][j] = d[1][i][j] = i == j?0:INF;
    }
}

void solve(vector<string> &input){
    string p1, p2, op;
    stringstream stream;
    mid = 0;
    init();
    for(int i=0;i<input.size();++i){
        stream.clear();
        //stream.str("");
        stream<<input[i];
        stream>>p1>>op>>p2;
        int a = getId(p1);
        int b = getId(p2);
        handle_input(a, b, op); 
    }
    if(!floyd_warshall(d[0])||!floyd_warshall(d[1])){
        cout<<"impossible"<<endl;
    }else{
        cout<<"possible"<<endl;
    }
}

int main(){
    vector<string> input;
    input.push_back("p1 N p3");
	input.push_back("p1 NW p5");
	input.push_back("p1 NW p2");
	input.push_back("p2 SW p6");
	input.push_back("p4 SW p6");
	input.push_back("p3 W p2");
	input.push_back("p4 S p1");
	input.push_back("p5 E p4");
	input.push_back("p1 W p6");
	input.push_back("p6 NE p5");//possible
    input.push_back("p7 N p2");
    input.push_back("p7 SE p6");//imposible
    solve(input);
}

/*
                p7?
          ________________
          | p1 |    | p6 |
		  _________________
		  | p3 | p2 |    |
		  ________________
		  | p4 | p5 |    |
		  ________________
          */

#include <iostream> 
#include <vector> 
#include <sstream>
#include <unordered_map>
#include <string>
#include <tuple>
using namespace std; 

bool pointsPossible(vector<string> input)
{
vector<tuple<string,string,int,int> > allinone;
for (int i=0;i<input.size();++i)
{
	istringstream ss;
	ss.str(input[i]);
	string p1,dir,p2;
	ss>>p1>>dir>>p2;
	string dirstr[8]={"S","W","N","E","SW","NW","SE","NE"};
	int x[8]={0,-1,0,1,-1,-1,1,1};
	int y[8]={-1,0,1,0,-1,1,-1,1};
	int pos;
	for (pos=0;pos<8 && dirstr[pos]!=dir;++pos) {}
	auto cur=make_tuple(p1,p2,x[pos],y[pos]);
	allinone.push_back(cur);
	for (int i=0;i<allinone.size();++i)
	{
	if (get<2>(allinone[i])==get<2>(cur) && get<3>(allinone[i])==get<3>(cur))
	{
	if (get<1>(allinone[i])==get<0>(cur))
	{allinone.push_back(make_tuple(get<0>(allinone[i]),get<1>(cur),get<2>(cur),get<3>(cur)));}	
	if (get<0>(allinone[i])==get<1>(cur))
	{allinone.push_back(make_tuple(get<0>(cur),get<1>(allinone[i]),get<2>(cur),get<3>(cur)));}	
	}
	}

	for (int i=0;i<allinone.size();++i)
	{
	cout<<get<0>(allinone[i])<<" "<<get<1>(allinone[i])<<" "<<get<2>(allinone[i])<<" "<<get<3>(allinone[i])<<" "<<endl;
	}

	for (int i=0;i<allinone.size();++i)
	{
	if (get<0>(allinone[i])==get<0>(cur) && get<1>(allinone[i])==get<1>(cur) && (get<2>(allinone[i])!=get<2>(cur) || get<3>(allinone[i])!=get<3>(cur))) return false;
	if (get<0>(allinone[i])==get<1>(cur) && get<1>(allinone[i])==get<0>(cur) && (get<2>(allinone[i])!=-get<2>(cur) || get<3>(allinone[i])!=-get<3>(cur))) return false;
	}
	cout<<endl;
}
return true;
}

int main()
{
string s1="p1 S p2";
string s2="p2 S p3";
string s5="p3 S p1";
string s3="p3 N p4";
string s4="p4 S p2";
vector<string> input;
input.push_back(s1);
input.push_back(s2);
input.push_back(s3);
input.push_back(s4);
input.push_back(s5);
cout<<pointsPossible(input)<<endl;
return 0;

}

First solution is right. The problem can be represented as a topologycal sorting where nodes represents coordinates.

enum DIRECTS{S=4, W=3, N=2, E=1, SW=12, NW=6, SE=9, NE=3};
typedef unsigned char Byte;
struct Data{
    int i;
    DIRECTS op;
    int j;
    Data(int ii, DIRECTS oop, int jj):i(ii), op(oop), j(jj){}
};

bool validPoints(vector<Data> &dset){
    if(dset.empty()) return true;
    unordered_map<int, Byte> hmap;
    for(auto &e:dset){
        if(hmap.find(e.i)==hmap.end())
            hmap[e.i] = 0;
        Byte j = hmap[e.i] ^ e.op;
        if(hmap.find(e.j)!=hmap.end() && hmap[e.j]&j!=0)
            return false;
        hmap[e.j] = j;
    }
    return true;
}

Here is an O(nlogn). Basically, do a merge sort but count inversions while merging.

package com.algo;

public class CountInversions {

	public static void main(String[] args) {

		int[] values = { 11, 4, 5, 8, 1, 3, 25 };

		int inversions = countInversions(values);
		System.out.println(inversions);

	}

	private static int countInversions(int[] values) {
		return countInversions(values, 0, values.length);
	}

	private static int countInversions(int[] values, int start, int end) {

		if (start == end || start + 1 == end) {
			return 0;
		} else {
			int mid = start + (end - start) / 2;
			return countInversions(values, start, mid) + countInversions(values, mid, end)
					+ merge(values, start, mid, mid, end);
		}

	}

	// 7, 11, 11, 16
	// 7,8,9,10,11,12,13,14,15
	// 11 - 7 + 16 - 11
	private static int merge(int[] values, int start1, int end1, int start2, int end2) {

		int inversions = 0;

		int length1 = end1 - start1;
		int length2 = end2 - start2;

		int[] mergedValues = new int[length1 + length2];

		int p1 = start1;
		int p2 = start2;

		int m = 0;
		while (p1 < end1 && p2 < end2) {

			if (values[p2] < values[p1]) {
				mergedValues[m] = values[p2];
				inversions += end1 - p1;
				p2++;
			} else {
				mergedValues[m] = values[p1];
				p1++;
			}

			m++;
		}

		while (p1 < end1) {
			mergedValues[m] = values[p1];
			m++;
			p1++;
		}

		while (p2 < end2) {
			mergedValues[m] = values[p2];
			m++;
			p2++;
		}

		m = 0;
		for (int i = start1; i < end2; i++) {
			values[i] = mergedValues[m];
			m++;
		}

		return inversions;
	}

}

Based on wws's comment, we can simulate the whole process:

For every maximum connected subgraph:
We random select a point and assign its position (0,0)
For every new point that is connected to this point, calculate their positions.
Select the new point, and for every point that is connected to this, if the point has position, check whether it is right, otherwise, calculate it and keep it.
Do this process until all the edges has been checked.

Example:
p0 W p1, p1 SW p2, p2 SE p3, p3 NE p0,p6 W p7
We can easily judge that (p0,p1,p2,p3) and (p6,p7) are maximum connected subgraph.
For (p0,p1,p2,p3):
We assign p0 (0,0)
p0 W p1 => p1 (1,0)
p1 SW p2 => p2 (2,1)
p2 SE p3 => p3(1,2)
p3 NE p0 => we know p0, so check whether p3 NE p0 => False

Of course sometimes when we select p0 and assign the coordinator, but edges connected to p0 would be mentioned later. So we'd better store all the connected points for every point.

vector<PointRel> v[N]; //store those point relation connect to point i
Point point[N];     // store position of the point i
bool pos[N];        // whether we know the position of point i
bool tag[N];        //whether point i has been checked 
stack<Point> s;
for(i=0;i<N;i++)
{
  if(tag[i])continue; //the related connected subgraph has been checked
  point[i]=(0,0)
  pos[i]=true
  s.push(i)
  while(!s.empty()){
    x = s.pop()
    for(j=0;j<v[x].size();j++)
       if(pos[v[x][j]] and !checkRelation(x,v[x][j]))return false
       else{ point[v[x][j]]=calPos(x,v[x][j]); pos[v[x][j]]=true;s.push(v[x][j]);}
    tag[i]=true
  }
}
return true