Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import std.stdio;
- import std.file;
- import std.conv;
- import std.string:munch;
- import std.math;
- import std.regex;
- class Segment{
- int x1, x2;
- double m, b;
- this( int x1, int y1, int x2, int y2 ){
- this.x1 = x1;
- this.x2 = x2;
- this.m = (y2 - y1)/cast(double)(x2 - x1);
- this.b = m * (0 - x1) + y1;
- }
- bool intersects(Segment s){
- if ( abs( this.m - s.m ) < .001 )
- return false;
- double x = -(this.b - s.b)/(this.m - s.m);
- return (x - this.x1)*(x - this.x2) < -.0001 && (x - s.x1)*(x - s.x2) < -.0001;
- }
- }
- struct Globals{
- int[][] knightMoves = [[2, 1], [2, -1], [-2, 1], [-2, -1],
- [1, 2], [1, -2], [-1, 2], [-1, -2]];
- int[][] comp;
- Segment[] segList;
- int N;
- int idx = 0;
- string[] nums;
- }
- static bool isOpen( Segment seg, ref Globals g ) {
- foreach( Segment s ; g.segList )
- if(seg.intersects(s))
- return false;
- return true;
- }
- static bool legal( int x, int y, ref Globals g ) {
- return x >= 0 && y >= 0 && x <= g.N && y <= g.N;
- }
- static bool wins( ref Globals g ) {
- for (int y = 1; y < g.N; y++)
- if (g.comp[0][y] > 0)
- for (int y2 = 1; y2 < g.N; y2++)
- if (g.comp[0][y] == g.comp[g.N][y2])
- return true;
- return false;
- }
- static bool solve( string f, ref Globals g ) {
- int newComp = 1;
- int M = nextInt( g );
- munch( f, " \t\n\r" );
- g.comp = new int[][](g.N+1, g.N+1);
- for (int i = 0; i < M; i++) {
- int player = (i % 2 == 0) ? 1: -1;
- int x = nextInt( g ), y = nextInt( g );
- g.comp[x][y] = player * newComp++;
- foreach(int[] del ; g.knightMoves) {
- int kx = x + del[0], ky = y + del[1];
- if( !legal( kx, ky, g ) )
- continue;
- int otherComp = g.comp[kx][ky];
- Segment seg = new Segment( x, y, kx, ky );
- if( otherComp * player > 0 && isOpen( seg, g ) ) {
- g.segList ~= seg;
- if (otherComp != g.comp[x][y])
- for(int px = 0; px <= g.N; px++)
- for (int py = 0; py <= g.N; py++)
- if (g.comp[px][py] == otherComp)
- g.comp[px][py] = g.comp[x][y];
- }
- }
- }
- return wins( g );
- }
- int nextInt( ref Globals g ){
- int next = to!int( g.nums[ g.idx++ ] );
- return next;
- }
- void main(){
- auto file = File("connect.in", "r");
- auto r = regex( "\\s" );
- string[] nums;
- string f = "";
- Globals g;
- foreach(string line; lines( file )){
- f ~= line; // throw the lines into a string
- }
- g.nums = split( f, r );
- g.N = nextInt( g );
- while(g.N > 0){
- writeln( solve( f, g ) ? "yes" : "no" );
- g.N = nextInt( g );
- }
- }
Add Comment
Please, Sign In to add comment