• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Jan 3rd, 2019 110 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import std.stdio;
2. import std.file;
3. import std.conv;
4. import std.string:munch;
5. import std.math;
6. import std.regex;
7.
8. class Segment{
9.     int x1, x2;
10.     double m, b;
11.
12.     this( int x1, int y1, int x2, int y2 ){
13.         this.x1 = x1;
14.         this.x2 = x2;
15.         this.m = (y2 - y1)/cast(double)(x2 - x1);
16.         this.b = m * (0 - x1) + y1;
17.     }
18.
19.     bool intersects(Segment s){
20.         if ( abs( this.m - s.m ) < .001 )
21.             return false;
22.         double x = -(this.b - s.b)/(this.m - s.m);
23.         return (x - this.x1)*(x - this.x2) < -.0001 && (x - s.x1)*(x - s.x2) < -.0001;
24.     }
25. }
26.
27. struct Globals{
28.     int[][] knightMoves = [[2, 1], [2, -1], [-2, 1], [-2, -1],
29.                                  [1, 2], [1, -2], [-1, 2], [-1, -2]];
30.     int[][] comp;
31.     Segment[] segList;
32.     int N;
33.     int idx = 0;
34.     string[] nums;
35. }
36.
37. static bool isOpen( Segment seg, ref Globals g ) {
38.     foreach( Segment s ; g.segList )
39.       if(seg.intersects(s))
40.         return false;
41.     return true;
42. }
43.
44. static bool legal( int x, int y, ref Globals g ) {
45.     return x >= 0 && y >= 0 && x <= g.N && y <= g.N;
46. }
47.
48. static bool wins( ref Globals g ) {
49.     for (int y = 1; y < g.N; y++)
50.        if (g.comp[0][y] > 0)
51.          for (int y2 = 1; y2 < g.N; y2++)
52.            if (g.comp[0][y] == g.comp[g.N][y2])
53.              return true;
54.     return false;
55. }
56.
57. static bool solve( string f, ref Globals g ) {
58.     int newComp = 1;
59.     int M = nextInt( g );
60.     munch( f, " \t\n\r" );
61.     g.comp = new int[][](g.N+1, g.N+1);
62.     for (int i = 0; i < M; i++) {
63.       int player = (i % 2 == 0) ? 1: -1;
64.       int x = nextInt( g ), y = nextInt( g );
65.       g.comp[x][y] = player * newComp++;
66.       foreach(int[] del ; g.knightMoves) {
67.         int kx = x + del[0], ky = y + del[1];
68.         if( !legal( kx, ky, g ) )
69.           continue;
70.         int otherComp = g.comp[kx][ky];
71.         Segment seg = new Segment( x, y, kx, ky );
72.         if( otherComp * player > 0 && isOpen( seg, g ) ) {
73.           g.segList ~= seg;
74.           if (otherComp != g.comp[x][y])
75.             for(int px = 0; px <= g.N; px++)
76.               for (int py = 0; py <= g.N; py++)
77.                 if (g.comp[px][py] == otherComp)
78.                   g.comp[px][py] = g.comp[x][y];
79.         }
80.       }
81.     }
82.     return wins( g );
83. }
84.
85. int nextInt( ref Globals g ){
86.     int next = to!int( g.nums[ g.idx++ ] );
87.     return next;
88. }
89.
90. void main(){
91.     auto file = File("connect.in", "r");
92.     auto r = regex( "\\s" );
93.     string[] nums;
94.     string f = "";
95.     Globals g;
96.
97.     foreach(string line; lines( file )){
98.         f ~= line; // throw the lines into a string
99.     }
100.
101.     g.nums = split( f, r );
102.
103.     g.N = nextInt( g );
104.     while(g.N > 0){
105.         writeln( solve( f, g ) ? "yes" : "no" );
106.         g.N = nextInt( g );
107.     }
108. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top