Guest User

Untitled

a guest
Jan 3rd, 2019
212
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
D 2.80 KB | None | 0 0
  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. }
Add Comment
Please, Sign In to add comment