//package delaune;

import java.math.*;
import java.io.*;
import java.util.*;
import java.applet.*;
import javax.swing.*;


public class Triangle {
  Point2D[] pointArray ;     //tasku masyvas
  Edge[] edgeArray;          //briaunu masyvas
  int point_number;
  int edge_number;
  int maxEdges;
  int s;
  int t;
  static final int Undefined = -1;

  public Triangle(int point_number) {
    this.point_number=point_number;
    pointArray = new Point2D [point_number];
    for (int i = 0;  i < point_number;  i++){
      pointArray[i] =new Point2D(0,0);
    }
    GeneratePointArray();           // sugeneruojam taskus pagal destytojo metoda

    maxEdges = 4 * point_number;    // inicijavimas briaunu
    edgeArray = new Edge[maxEdges];
    for (int i = 0; i < maxEdges; i++)
      edgeArray[i] = new Edge();
    edge_number = 0;

  }


  public void GeneratePointArray(){
    int[] x=randperm(point_number,null);
    int[] y=randperm(point_number,x);
    for (int i=0;i<point_number;i++){
      pointArray[i].y = y[i];
      pointArray[i].x=x[i];
    }

  }

public static int[] randperm(int point_number,int[] j0){
  Random R=new Random(point_number+((long)point_number)<<31);
  int[] j = new int[point_number];
  int w,k;
  if (j0==null)	for (int i=0; i<point_number; i++) j[i]=i;
  else	for (int i=0; i<point_number; i++) j[i]=j0[i];
  for (int i=0; i<point_number; i++) {
    w=(int)(point_number*R.nextDouble());
    if (w==point_number) w=point_number-1;
    k=j[i]; j[i]=j[w]; j[w]=k;
  }
  return j;
}

public void findClosestPoints() {
    int i, j;
    float d, min;
    int u, v;

    u = v = 0;
    min = Float.MAX_VALUE;
    for (i = 0; i < point_number-1; i++)
      for (j = i+1; j < point_number; j++){
        d = pointArray[i].distance(pointArray[j]);
        if (d < min){
          u = i;
          v = j;
          min = d;
        }
      }
    s=u;
    t=v;
  }


void addTriangle(int s, int t, int u) {
  addEdge(s, t);
  addEdge(t, u);
  addEdge(u, s);
}

public int addEdge(int s, int t) {
  return addEdge(s, t, Undefined, Undefined);
}


public int addEdge(int s, int t, int l, int r) {
  int e;
  e = findEdge(s, t);
  if (e == Undefined){
    edgeArray[edge_number].s = s;
    edgeArray[edge_number].t = t;
    edgeArray[edge_number].l = l;
    edgeArray[edge_number].r = r;
    return edge_number++;
  }
  else
    return Undefined;
}

public int findEdge(int s, int t) {
  boolean edgeExists = false;
  int i;
  for (i = 0; i < edge_number; i++)
    if (edgeArray[i].s == s && edgeArray[i].t == t ||
        edgeArray[i].s == t && edgeArray[i].t == s) {
      edgeExists = true;
      break;
    }

  if (edgeExists)
    return i;
  else
    return Undefined;
}


public void updateEdge(int eI, int s, int t) {

  if (edgeArray[eI].s == s && edgeArray[eI].l == Triangle.Undefined)
    edgeArray[eI].l = 1;
  else if (edgeArray[eI].t == s && edgeArray[eI].r == Triangle.Undefined)
    edgeArray[eI].r = 1;
}
}