import daj.*;
import java.math.*;

class ConvexHullNode extends Program {
  public int x,y;
  public int n;
  public int N;
  public PointSet S;
  public int k;

  public PointSet CH;
  public PointSet Region[] = new PointSet[4];

  private Position xmin = null, xmax = null, ymin = null, ymax = null;
  
  private DrawWindow window;

  
  /////////////////////////////////////////////////////////////////////////////////
  //
  // basic communication
  //
  /////////////////////////////////////////////////////////////////////////////////
  
  private int colParentChannel;
  private int rowParentChannel;
  private int nRowChildren;
  private int nColChildren;


  //
  // do a min operation within a row
  //
  private Position rowReduce(Position value) {

    // recv. from children and compare with own value
    for(int i=0; i < nRowChildren; i++) {
      Position msgChild = 
	(Position)(in().getChannel(rowParentChannel+1+i).receive());

      if(msgChild.val < value.val) {
	value = msgChild;
      }
    }

    // send to parrent if one exists
    if(x != 0) {
      out().getChannel(rowParentChannel).send(new Position(value) );
    }
    
    return value;
  }

  //
  // do a min operation within a columns
  //
  private Position colReduce(Position value) {

    // recv. from children and compare with own value
    for(int i=0; i < nColChildren; i++) {
      Position msgChild = 
	(Position)(in().getChannel(colParentChannel+1+i).receive());

      if(msgChild.val < value.val) {
	value = msgChild;
      }
    }

    // send to parrent if one exists
    if(y != 0) {
      out().getChannel(colParentChannel).send(new Position(value) );
    }
    
    return value;
  }

  //
  // do a broadcast along a row
  //
  private Message rowBcast(Message msg) {
    // get from parent, if one exists
    if(x != 0)
      msg = in().getChannel(rowParentChannel).receive();
    
    // send to children
    for(int i=0; i < nRowChildren; i++) 
      out().getChannel(rowParentChannel + 1 + i).send(msg);

    return msg;
  }

  //
  // do a broadcast along a columns
  //
  private Message colBcast(Message msg) {
    // get from parent, if one exists
    if(y != 0)
      msg = in().getChannel(colParentChannel).receive();
    
    // send to children
    for(int i=0; i < nColChildren; i++) 
      out().getChannel(colParentChannel + 1 + i).send(msg);

    return msg;
  }

  //
  // send a message from column p to column 0
  //
  private Message rowRoot(int p, Message msg) {

    if(p == 0)			// reached root
      return msg;

    if(p == x) {
      out().getChannel(rowParentChannel).send(msg);
    }
    int p1 = (p-1)/2;
    if(p1 == x) {
      if( (p % 2) == 0) {	// p even -> second child
	msg = in().getChannel(rowParentChannel + 2).receive();
      } else {			// p odd -> first child
	msg = in().getChannel(rowParentChannel + 1).receive();
      }
    }
    
    return rowRoot(p1, msg);
  }

  //
  // send a message from row p to row 0
  //
  private Message colRoot(int p, Message msg) {

    if(p == 0)			// reached root
      return msg;

    if(p == y) {
      out().getChannel(colParentChannel).send(msg);
    }
    int p1 = (p-1)/2;
    if(p1 == y) {
      if( (p % 2) == 0) {	// p even -> second child
	msg = in().getChannel(colParentChannel + 2).receive();
      } else {			// p odd -> first child
	msg = in().getChannel(colParentChannel + 1).receive();
      }
    }
    
    return colRoot(p1, msg);
  }

  /////////////////////////////////////////////////////////////////////////////////
  //
  // basic geometric operations
  //
  /////////////////////////////////////////////////////////////////////////////////

  private double slope(Point p1, Point p2) {
    return (p1.y - p2.y) / (p1.x - p2.x);
  }


  private double polar(Point p, double x0, double y0) {
    double x = p.x - x0;
    double y = p.y - y0;

    return Math.atan2(x,y);
  }


  /////////////////////////////////////////////////////////////////////////////////

  

  public ConvexHullNode(DrawWindow window, int x, int y, int n, int N) {
    this.window = window;

    this.x = x;
    this.y = y;
    this.n = n;
    this.N = N;

    k = n/N;

    // determine number of children in row and column direction
    if( (2*x + 2) < N )
      nRowChildren = 2;
    else if( (2*x + 1) < N)
      nRowChildren = 1;
    else
      nRowChildren = 0;

    if( (2*y + 2) < N )
      nColChildren = 2;
    else if( (2*y + 1) < N)
      nColChildren = 1;
    else
      nColChildren = 0;

    // find parent channel
    rowParentChannel = (x==0) ? -1 : 0;
    colParentChannel = (y==0) ? rowParentChannel + nRowChildren :
      rowParentChannel + nRowChildren + 1;

    CH = new PointSet(k + 8);
  }


  //
  // Initialisation
  //
  // construct S, and broadcast to the first 4 rows
  //
  private void initS() {
    
    switch(y) {
    case 0:			// row 0 constructs the Set
      // construct k points (uniformly distributed in [0,1]x[0,1])
      S = new PointSet(k);
      for(int i=0; i < k; i++) {
	//Point p = new Point(Math.random(),Math.random());
	// Point p = new Point(Math.sin( 2 * 3.1415 * (i + x*k)/n) * 0.5 + 0.5,
	//		    Math.cos( 2 * 3.1415 * (i + x*k)/n) * 0.5 + 0.5 );
	
	double r = Math.random() * 0.5;
	double a = Math.random() * 6.283185307;
	Point p = new Point( 0.5 + r * Math.sin(a),
			     0.5 + r * Math.cos(a));

	S.add(p);
	window.add(p, 0);
      }

      out().getChannel(colParentChannel + 1).send(S);
      out().getChannel(colParentChannel + 2).send(S);
      break;

    case 1:			/// row 1
      S = (PointSet)in().getChannel(colParentChannel).receive();
      out().getChannel(colParentChannel + 1).send(S);
      break;

    case 2: case 3:		// row 2 and 3
      S = (PointSet)in().getChannel(colParentChannel).receive();
    }
  }

  //
  // find extreme points
  //
  private void findExtremePoints() {
    switch(y) {
    case 0:
      xmin = new Position(S.p[0].x, S.p[0], 0, x);
      for(int i=1; i < k; i++) {
	if( S.p[i].x < xmin.val) {
	  xmin.val = S.p[i].x;
	  xmin.point = S.p[i];
	  xmin.pos = i;
	}
      }
      xmin = rowReduce(xmin);		
      break;

    case 1:
      xmax = new Position(S.p[0].x, S.p[0], 0, x);
      for(int i=1; i < k; i++) {
	if( S.p[i].x > xmax.val) {
	  xmax.val = S.p[i].x;
	  xmax.point = S.p[i];
	  xmax.pos = i;
	}
      }
      xmax.val = - xmax.val;
      xmax = rowReduce(xmax);
      xmax.val = - xmax.val;
      break;

    case 2:
      ymin = new Position(S.p[0].y, S.p[0], 0, x);
      for(int i=1; i < k; i++) {
	if( S.p[i].y < ymin.val) {
	  ymin.val = S.p[i].y;
	  ymin.point = S.p[i];
	  ymin.pos = i;
	}
      }
      ymin = rowReduce(ymin);		
      break;

    case 3:
      ymax = new Position(S.p[0].y, S.p[0], 0, x);
      for(int i=1; i < k; i++) {
	if( S.p[i].y > ymax.val) {
	  ymax.val = S.p[i].y;
	  ymax.point = S.p[i];
	  ymax.pos = i;
	}
      }
      ymax.val = - ymax.val;
      ymax = rowReduce(ymax);
      ymax.val = - ymax.val;
      break;
    }
  }

  //
  // send the extreme points to row 0 (in column 0)
  //
  private void collectExtremePoints() {
    if(x == 0) {
      switch(y) {
      case 3:
	out().getChannel(colParentChannel).send(ymax);
	break;
      case 2:
	out().getChannel(colParentChannel).send(ymin);
	break;
      case 1:
	ymax = (Position)in().getChannel(colParentChannel + 1).receive();
	out().getChannel(colParentChannel).send(ymax);
	out().getChannel(colParentChannel).send(xmax);
	break;
      case 0:
	ymax = (Position)in().getChannel(colParentChannel + 1).receive();
	xmax = (Position)in().getChannel(colParentChannel + 1).receive();
	ymin = (Position)in().getChannel(colParentChannel + 2).receive();

	// node 0,0 remebers the extreme points as part of the CH
	CH.add(xmin.point);
	CH.add(xmax.point);
	CH.add(ymin.point);
	CH.add(ymax.point);
	break;
      }
    }

    // draw extreme points
    if( (x == 0) && (y == 0)) {
      window.add(xmin.point, 1);
      window.add(xmax.point, 1);
      window.add(ymin.point, 1);
      window.add(ymax.point, 1);
      window.add(xmin.point, ymax.point, 0);
      window.add(ymax.point, xmax.point, 0);
      window.add(xmax.point, ymin.point, 0);
      window.add(ymin.point, xmin.point, 0);
    }
  }

  //
  // broadcast extereme points to all processors
  //
  private void bcastExtremePoints() {
    if(y == 0) {
      // broadcast the extreme points in the first row
      xmin = (Position)rowBcast(xmin);
      xmax = (Position)rowBcast(xmax);
      ymin = (Position)rowBcast(ymin);
      ymax = (Position)rowBcast(ymax);
    }
    // bcast along the columns
    xmin = (Position)colBcast(xmin);
    xmax = (Position)colBcast(xmax);
    ymin = (Position)colBcast(ymin);
    ymax = (Position)colBcast(ymax);
  }


  private void identifyRegions() {
    if(y == 0) {
      //
      // identify for all other points the region, and
      // remember extreme points as being part of CH(S)
      //

      double k1 = slope(xmax.point, ymin.point);
      double d1 = ymin.point.y - k1 * ymin.point.x;

      double k2 = slope(xmax.point, ymax.point);
      double d2 = ymax.point.y - k2 * ymax.point.x;

      double k3 = slope(ymax.point, xmin.point);
      double d3 = xmin.point.y - k3 * xmin.point.x;

      double k4 = slope(ymin.point, xmin.point);
      double d4 = xmin.point.y - k4 * xmin.point.x;

      Region[0] = new PointSet(k);
      Region[1] = new PointSet(k);
      Region[2] = new PointSet(k);
      Region[3] = new PointSet(k);

      for(int i=0; i < S.k; i++) {
	if( ! (( (xmin.proc == x) && (xmin.pos == i) ) ||
	       ( (xmax.proc == x) && (xmax.pos == i) ) ||
	       ( (ymin.proc == x) && (ymin.pos == i) ) ||
	       ( (ymax.proc == x) && (ymax.pos == i) ) ) ) {

	  // this is not an extreme point

	  if( (S.p[i].x > ymin.point.x) &&
	      (S.p[i].x < xmax.point.x) &&
	      (S.p[i].y < (k1 * S.p[i].x + d1) ) ) {		// region 1
	    Region[0].add(S.p[i]);
	    window.add(S.p[i], 2);
	  } else if( (S.p[i].x > ymax.point.x) &&
		     (S.p[i].x < xmax.point.x) &&
		     (S.p[i].y > (k2 * S.p[i].x + d2) ) ) {	// region 2
	    Region[1].add(S.p[i]);
	    window.add(S.p[i], 2);
	  } else if( (S.p[i].x > xmin.point.x) &&
		     (S.p[i].x < ymax.point.x) &&
		     (S.p[i].y > (k3 * S.p[i].x + d3) ) ) {	// region 3
	    Region[2].add(S.p[i]);
	    window.add(S.p[i], 2);
	  } else if( (S.p[i].x > xmin.point.x) &&
		     (S.p[i].x < ymin.point.x) &&
		     (S.p[i].y < (k4 * S.p[i].x + d4) ) ) {	// region 4
	    Region[3].add(S.p[i]);
	    window.add(S.p[i], 2);
	  }
	}
      }
    }
  }

  //
  // broadcast Region sets along columns
  //
  private void bcastRegions() {
    Region[0] = (PointSet)colBcast(Region[0]);
    Region[1] = (PointSet)colBcast(Region[1]);
    Region[2] = (PointSet)colBcast(Region[2]);
    Region[3] = (PointSet)colBcast(Region[3]);
  }



  private void identifyCH(int region) {
    
    // send the points from proc in the diagonal to column 0, and broadcast
    PointSet R = (PointSet)rowRoot(y, Region[region]);
    R = (PointSet)rowBcast(R);
    
    for(int i=0; i < R.k; i++) {		// all points that are potentially in CH
    
      Position pj = null;
      switch(region) {
      case 0: 			// compare with xmax
	pj = new Position(slope(R.p[i], xmax.point), xmax.point, -1, x);
	break;
      case 1:			// compare with xmax, but use negative slope
	pj = new Position(-slope(R.p[i], xmax.point), xmax.point, -1, x);
	break;
      case 2:			// compare with ymax, use negative slope
	pj = new Position(-slope(R.p[i], ymax.point), ymax.point, -1, x);
	break;
      case 3:			// compare with ymin
	pj = new Position(slope(R.p[i], ymin.point), ymin.point, -1, x);
	break;
      }
            
      
      // compare with all own points,
      // find the one with minimum angle (slope + rel. position w.r.t. x)
      for(int j=0; j < Region[region].k; j++) {
	
	if( R.p[i].x > Region[region].p[j].x )	// pi must be left of pj
	  continue;
	
	double k = slope(R.p[i], Region[region].p[j]);
	
	if( (region == 1) || (region == 2))	// here we need max. slope
	  k = -k;
	
	if( k < pj.val )			// better slope
	  pj = new Position(k, Region[region].p[j], j, x);
      }

      // find pj that forms minimal angle with pi, and broadcast
      pj = rowReduce(pj);
      pj = (Position)rowBcast(pj);
      

      // check, if all points fall on one side of (pi,pj)
      double k = ((region==1)||(region==2)) ? - pj.val : pj.val;
      double d = pj.point.y - k * pj.point.x;
      
      boolean allOnOneSide = true;
      
      switch(region) {
      case 0:
	if( k * ymin.point.x + d > ymin.point.y)
	  allOnOneSide = false;
	break;
      case 1:
	if( k * ymax.point.x + d < ymax.point.y)
	  allOnOneSide = false;
	break;
      case 2:
	if( k * xmin.point.x + d < xmin.point.y)
	  allOnOneSide = false;
	break;
      case 3:
	if( k * xmin.point.x + d > xmin.point.y)
	  allOnOneSide = false;
	break;
      }

      // test if all other points in the region fall on one side of (pi,pj)
      for(int t=0; (t < Region[region].k) && allOnOneSide; t++) {
	if( (pj.proc == x) && (pj.pos == t) )		// do not compare with pj
	  continue;
	if( (y == x) && (t == i) )			// do not compare with pi
	  continue;

	if((region==0)||(region==3)) {
	  if( k * Region[region].p[t].x + d > Region[region].p[t].y)
	    allOnOneSide = false;
	} else {
	  if( k * Region[region].p[t].x + d < Region[region].p[t].y)
	    allOnOneSide = false;
	}
      }
      
      // convert boolean to double for reduction operation
      double aOOS = allOnOneSide ? 1 : 0;
      aOOS = rowReduce( new Position(aOOS, null, 0, x) ).val;
      
      // if all-on-one-side: keep it
      if( (aOOS == 1) && (x == 0) ) {
	CH.add( R.p[i]);
	window.add( R.p[i], 3);
      }
    }
  }


  private void sortCH() {

    if(x==0) {
      // compute polar coordinates
      PositionSet CH_phi = new PositionSet( ((x == 0) && (y == 0)) ? n+4 : CH.k);
      double x0 = (xmax.point.x + xmin.point.x) / 2;
      double y0 = (ymax.point.y + ymin.point.y) / 2;
      for(int i=0; i < CH.k; i++) {
	CH_phi.add(new Position( polar(CH.p[i], x0, y0), CH.p[i], i,x) );
      }
      
      // send all point to proc 0,0
      for(int i=1; i < N; i++) {
	PositionSet CH_phi1 = (PositionSet)colRoot(i, CH_phi);

	if( y == 0) {
	  for(int j=0; j < CH_phi1.k; j ++)
	    CH_phi.add(CH_phi1.p[j]);
	}
      }

      // sort only on proc 0,0
      if(y == 0) {
	CH = new PointSet(CH_phi.k);

	// just bubble sort
	boolean chg = true;
	while(chg) {
	  chg = false;
	  for(int i=1; i < CH_phi.k; i++)
	    if(CH_phi.p[i-1].val > CH_phi.p[i].val) {
	      Position t = CH_phi.p[i-1];
	      CH_phi.p[i-1] = CH_phi.p[i];
	      CH_phi.p[i] = t;
	      chg = true;
	    }
	}

	// copy back
	for(int i=0; i < CH_phi.k; i++)
	  CH.add(CH_phi.p[i].point);

	// and draw
	for(int i=1; i < CH.k; i++) {
	  window.add( CH.p[i-1], CH.p[i], 1);
	}
	window.add( CH.p[0], CH.p[CH.k-1], 1);
      }
    }
  }

  
  public void main() {

    initS();
    
    // Stage 1
    findExtremePoints();
    collectExtremePoints();
    bcastExtremePoints();

    // Stage 2
    identifyRegions();
    bcastRegions();
    
    // Stage 3
    for(int region=0; region < 4; region ++)
      identifyCH(region);

    // Stage 4
    sortCH();
  }
}