CareerCup

how about getting all connected components in the graph: run dfs to get all connected components -> every pair of straws in a connected component is connected

1. Develop an Algorithm to find if two given Line segments intersect
Given two points find
y2 - y1
m1 = ------------- and like wise m2 for line
x2 - x1

Now Line can be y = m * x + b
You get such two equations for each line. Subtract both equations to get y and x of intersection.

2. Check if the Intersection point is actually fall within the rectangle of intersection of both line segments . To do that make sure X is within Min of Right X and Max of the left X. Like wise make sure that Y is within max of bottom Y and Min of Top Y.

Well above two steps tell you whether two lines intersect or not. Now lets build the solution for game using it.

How about a plain old greed map-coloring approach? Complexity is O(n m) and memory is O(n) where n is the number of students and m is the number of known friends. Depending on how the number of known students is determines, the Complexity may be closer to O(n^2).

Assumptions:
-Students are treated as Ids
-the lookup table is accessible via a function "int[] getKnown(int studentId)"

public static int getNumColors(int[] students){
    if(students == null){
        throw new NullPointerException();
    }

    HashMap<Integer, Integer> studentToTableMap = new HashMap<Integer, Integer>(students.length);
    int numTables = 0;
    for(int studentId : students){
        int[] known = getKnown(studentId);
        HashSet<Integer> peerTables = new HashSet<Integer>();
        for(int knownId : known){
            Integer table = studentToTableMap.get(knownId);
            if(table != null){
                peerTables.add(table);
            }
        }
        int tableCount = 1;
        while(peerTables.contains(tableCount)){
            tableCount++;
        }
        studentToTableMap.put(studentId, tableCount);
        if(tableCount > numTables){
            numTables = tableCount;
        }
    }
    return numTables;
}

Here is what i think of a solution for this problem
First we define the structure of a straw.

Class Straw
{
	int X_1, Y_1;// this is to repersent first  coordinate of the straw
	int X_2,Y_2;//secon coordinate
}

Now we are given N list of straws as input.
Lets first define how two straw are connected to each other or not(we can consider this problem as to figure out whether two lines of 2D are intersecting/touching each or or not).
We are use the Cross product to figure out this.

bool IsIntersect(Straw a, Straw b)
	Define 	P1 = (a.X_1,a.Y_1);P2 = (a.X_2,a.Y_2);
			P3 = (b.X_1,b.Y_1);P4 = (b.X_2,b.Y_2);

we can use following cross products to figure out whether these two straws intersecting/touching each other or not

If Cross_Product(P1P2, P1P4) and Cross_Product(P1P2,P1P3) are apposite to each other and Cross_Product(P3P4, P3P1) and Cross_Product(P3P4,P3P2) are also apposite to each other then these two straws are intersecting, other wise if any of the cross_product is zero, which is the case when these two straws are touching each other or are their in a single line, then we just check the vertices of other lines, if any one of thems((p1 or p2) or (p3 or p4))'s x and y coordinate lies between other line's coordinetes.

Now we will start the actual execution.
We will keep three array of indexes, one which will have indexes straws in non decreasing order x coordinate
other two will have non decreasing order of y coordinate of first and second vertices.
now we will figure out the connected component.
Please note that any straw from one connected component will only touch/intersect other straws of the same component.
Here is the algorithm

A <- Input straws
Index_x <- indexes in nondecreasing order of min of x(from both the vertices of a straw)
Index_y_1 <- indexes in nondecreasing order of y_1
Index_y_2 <- indexes in nondecreasing order of y_2
In index_x, we also keep one flag to tell whether something is left to try or not
keep a queue Q = empty(normal queue)
while(something left in index_x to try) 
    take the first untried index, call it j, set tried flag to true;
    figure out the list of straws which may intersect/touch with straw j
    We can figure out by first figure out the list of untried straws using index_x, where index_x's straw's min x <= j' straws max x.
    then we will also figure out the list of untried straws using index_y_1 and index_y_2.where ay straws whose either first y coordinate or second y coordinate lies between J's straws min y and max y coordinate.
      we will put all these straws in the Q
      while(Q is not empty)
          straw_k <- Dequeue();
          if straw_k and straw_j are connected, then insert k into an array, and set k as tried
               figure out all the possible untried straws which may intersect with k using above logic and insert them also into the queue 
     insert a seperator into the array to defferenciate between connected component.

print the connected component and any two straw from a connected component are touching/intersecting each other directly or indirectly.

the complexity is :

Time : O(n * log(n)) for sorting + O(n * k * log(n)) where k is degree of connectivity of straws,
space : O(n), or more preciously 5N.

const int INF = 1 << 30;
1. const int MaxN = 100005;
2. const double eps = 1e-9;
3.
4. int sgn(double d)
5. {
6. if(d > eps) return 1;
7. if(d < -eps) return -1;
8. return 0;
9. }
10.
11. struct Point
12. {
13. int x, y;
14. Point() {}
15. Point(int _x, int _y) : x(_x), y(_y) {}
16. void read()
17. {
18. scanf("%d%d", &x, &y);
19. }
20. };
21. Point pnt[15][3];
22. int n;
23. int a, b;
24. bool con[15][15];
25. bool vis[15];
26.
27. Point operator - (const Point &p1, const Point &p2)
28. {
29. return Point(p1.x - p2.x, p1.y - p2.y);
30. }
31.
32. double operator * (const Point &p1, const Point &p2)
33. {
34. return (double)(p1.x * p2.y - p1.y * p2.x);
35. }
36.
37. bool get_line_intersection(const Point &p1, const Point &p2, const Point &p3, const Point &p4)
38. {
39. double d1 = (p2 - p1) * (p3 - p1);
40. double d2 = (p2 - p1) * (p4 - p1);
41. if(0 == sgn(d1 - d2)) return false;
42. return true;
43. }
44.
45. bool get_segment_intersection(const Point &p1, const Point &p2, const Point &p3, const Point &p4)
46. {
47. if(!get_line_intersection(p1, p2, p3, p4)) {
48. if(min(p1.x, p2.x) > max(p3.x, p4.x) || min(p3.x, p4.x) > max(p1.x, p2.x)) return false;
49. if(min(p1.y, p2.y) > max(p3.y, p4.y) || min(p3.y, p4.y) > max(p1.y, p2.y)) return false;
50. return true;
51. }
52. double d1 = (p2 - p1) * (p3 - p1);
53. double d2 = (p2 - p1) * (p4 - p1);
54. double d3 = (p4 - p3) * (p1 - p3);
55. double d4 = (p4 - p3) * (p2 - p3);
56. int s1 = sgn(d1), s2 = sgn(d2), s3 = sgn(d3), s4 = sgn(d4);
57. if(s1 * s2 > 0 || s3 * s4 > 0 || sgn(d1 - d2) == 0) return false;
58. return true;
59. }
60.
61.
62. bool gao(int x, int y)
63. {
64. if(con[x][y]) return true;
65. vis[x] = true;
66. repf(i, 1, n) {
67. if(!vis[i] && con[x][i]) {
68. vis[i] = true;
69. bool f = gao(i, y);
70. if(f) return true;
71. }
72. }
73. return false;
74. }
75.
76. int main()
77. {
78. while(1 == scanf("%d", &n) && n > 0) {
79. repf(i, 1, n) {
80. pnt[i][0].read();
81. pnt[i][1].read();
82. }
83. mset(con, false);
84. repf(i, 1, n) repf(j, 1, n) {
85. if(i == j) con[i][j] = true;
86. else con[i][j] = get_segment_intersection(pnt[i][0], pnt[i][1], pnt[j][0], pnt[j][1]);
87. }
88. while(2 == scanf("%d%d", &a, &b)) {
89. if(a == 0 && b == 0) break;
90. mset(vis, false);
91. if(gao(a, b)) puts("CONNECTED");
92. else puts("NOT CONNECTED");
93. }
94. }
95. return 0;
96. }