-------------------------Sim-------------------------

/**********************************/
/*     巡回セールスマン問題を解く */
/*          coded by Y.Suganuma   */
/**********************************/
import java.io.*;

public class Sim {
	public static void main(String args[]) throws IOException
	{
		Data dt = new Data();
	}
}

-------------------------Data-------------------------

/**********************************/
/*     巡回セールスマン問題を解く */
/*          coded by Y.Suganuma   */
/**********************************/
import java.io.*;
import java.awt.*;
import java.awt.event.*;
import java.applet.*;

class Data extends Frame implements ItemListener, ActionListener {

	int kind = 10;   // =10 : １０都市
                     // =20 : ２０都市
	Button bt;
	Choice choice;

	/**********************/
	/*     コンストラクタ */
	/**********************/
	Data()
	{
						// Frameクラスのコンストラクタの呼び出し
		super("データの入力");
						// レイアウトの変更
		setLayout(new GridLayout(2, 2, 5, 10));
						// スクロールリスト（都市の数）
		setFont(new Font("TimesRoman", Font.PLAIN, 20));

		Label lbl1 = new Label("都市の数");
		add(lbl1);
		choice = new Choice();
		choice.add("１０都市");
		choice.add("２０都市");
		add(choice);
		choice.addItemListener(this);
						// OK ボタンの設定
		Label lbl2 = new Label();
		add(lbl2);
		bt = new Button("OK");
		bt.addActionListener(this);
		add(bt);
						// Windowサイズを設定
		setSize(300, 200);
						// ウィンドウを表示
		setVisible(true);
						// イベントアダプタ
		addWindowListener(new WinEnd());
	}

	/**********************************/
	/*     上，左，下，右の余白の設定 */
	/**********************************/
	public Insets getInsets()
	{
		return new Insets(70, 20, 20, 20);
	}

	/**********************************/
	/*     チョイスコントロールの処理 */
	/**********************************/
	public void itemStateChanged(ItemEvent e)
	{
		if (e.getItemSelectable() == choice) {
			kind = ((Choice)e.getItemSelectable()).getSelectedIndex();
			kind = (kind <= 0) ? 10 : 20;
		}
	}

	/************************************/
	/*     OKボタンが押されたときの処理 */
	/************************************/
	public void actionPerformed(ActionEvent e)
	{
		if (e.getSource() == bt) {
			TSP tsp = new TSP (kind);
			tsp.repaint();
		}
	}

	/****************/
	/*     終了処理 */
	/****************/
	class WinEnd extends WindowAdapter
	{
		public void windowClosing(WindowEvent e) {
			System.exit(0);
		}
	}
}

-------------------------TSP-------------------------

/****************************/
/*     巡回セールスマン問題 */
/****************************/
import java.io.*;
import java.awt.*;
import java.awt.event.*;

class TSP extends Frame {

	private double ritu;   // 表示倍率
	private int size;   // 都市を示す丸の大きさ
	private int font;   // フォントサイズ
	private int min_x, max_x, min_y, max_y;   // 都市の存在範囲
	private int width, height;   // 画面の大きさ
	private int yoyu_x, yoyu_y;   // 表示位置
	private int con[][];   // 接続状態
	private int city[][];   // 各都市の位置
	private int rg[][];   // 各都市間の距離
	private int n_city;   // 都市の数
	private int pos1;   // 前回マウスが押された都市
	private String str;   // メッセージ
	private TSP tsp = this;

	/********************************/
	/*     コンストラクタ           */
	/*          kd : =10 : １０都市 */
	/*               =20 : ２０都市 */
	/********************************/
	TSP (int kd)
	{
					// Frameクラスのコンストラクタの呼び出し
		super("巡回セールスマン問題");
					// 値の設定と領域の確保
		double k1, k2, x, y;
		int i1, i2;

		n_city = kd;
		font   = 15;
		size   = 10;
		yoyu_x = 50;
		yoyu_y = 100;
		width  = 1000;
		height = 700;
		pos1   = -1;
		str    = "***Start***";
		con    = new int [n_city][n_city];
		city   = new int [n_city][2];

		if (n_city == 10) {
			city[0][0] = -58;
			city[1][0] = 55;
			city[2][0] = 6;
			city[3][0] = 27;
			city[4][0] = 44;
			city[5][0] = 33;
			city[6][0] = -94;
			city[7][0] = -9;
			city[8][0] = 33;
			city[9][0] = 43;
			city[0][1] = 37;
			city[1][1] = -19;
			city[2][1] = -79;
			city[3][1] = -30;
			city[4][1] = -94;
			city[5][1] = -58;
			city[6][1] = 87;
			city[7][1] = 3;
			city[8][1] = 69;
			city[9][1] = -57;
		}
		else {
			city[0][0]  = 31;
			city[1][0]  = 34;
			city[2][0]  = 3;
			city[3][0]  = 20;
			city[4][0]  = -48;
			city[5][0]  = 65;
			city[6][0]  = -40;
			city[7][0]  = 57;
			city[8][0]  = 60;
			city[9][0]  = 7;
			city[10][0] = -50;
			city[11][0] = 43;
			city[12][0] = -34;
			city[13][0] = 41;
			city[14][0] = -65;
			city[15][0] = 56;
			city[16][0] = 19;
			city[17][0] = 11;
			city[18][0] = -20;
			city[19][0] = 29;
			city[0][1]  = -39;
			city[1][1]  = -78;
			city[2][1]  = -2;
			city[3][1]  = -26;
			city[4][1]  = -25;
			city[5][1]  = -65;
			city[6][1]  = 28;
			city[7][1]  = 97;
			city[8][1]  = -7;
			city[9][1]  = 25;
			city[10][1] = 40;
			city[11][1] = 95;
			city[12][1] = -10;
			city[13][1] = 47;
			city[14][1] = -96;
			city[15][1] = -91;
			city[16][1] = -50;
			city[17][1] = 3;
			city[18][1] = -63;
			city[19][1] = 43;
		}

		rg = new int [n_city][n_city];
		for (i1 = 0; i1 < n_city; i1++) {
			for (i2 = 0; i2 < i1; i2++) {
				x           = city[i2][0] - city[i1][0];
				y           = city[i2][1] - city[i1][1];
				rg[i1][i2]  = (int)(Math.sqrt(x * x + y * y) + 0.5);
				rg[i2][i1]  = rg[i1][i2];
				con[i1][i2] = 0;
				con[i2][i1] = 0;
			}
			rg[i1][i1]  = 0;
			con[i1][i2] = 0;
		}
					// 描画領域の計算
		min_x = (int)city[0][0];
		max_x = (int)city[0][0];
		min_y = (int)city[0][1];
		max_y = (int)city[0][1];

		for (i1 = 1; i1 < n_city; i1++) {
			if ((int)city[i1][0] < min_x)
				min_x = (int)city[i1][0];
			else {
				if ((int)city[i1][0] > max_x)
					max_x = (int)city[i1][0];
			}
			if ((int)city[i1][1] < min_y)
				min_y = (int)city[i1][1];
			else {
				if ((int)city[i1][1] > max_y)
					max_y = (int)city[i1][1];
			}
		}

		k1   = (double)(width - 2 * yoyu_x) / (max_x - min_x);
		k2   = (double)(height - yoyu_y - yoyu_x) / (max_y - min_y);
		ritu = (k1 < k2) ? k1 : k2;
					// Windowサイズ
		width  = 2 * yoyu_x + (int)(ritu * (max_x - min_x));
		height = yoyu_y + yoyu_x + (int)(ritu * (max_y - min_y));
		setSize(width, height);
					// ウィンドウを表示
		setVisible(true);
					// イベントアダプタ
		addWindowListener(new WinEnd());
		addMouseListener(new ClickMouse());
	}

	/************/
	/*     描画 */
	/************/
	public void paint (Graphics g)
	{
		int i1, i2, x1, x2, y1, y2, p = size / 2, r;
					// メッセージ
		Font f = new Font("TimesRoman", Font.BOLD, font+5);
		g.setFont(f);
		g.setColor(Color.blue);
						// メッセージ
		if (str.length() > 0)
			g.drawString(str, yoyu_x-30, yoyu_y-50);
						// 距離の出力
		else {
			r = 0;
			for (i1 = 0; i1 < n_city; i1++) {
				for (i2 = i1+1; i2 < n_city; i2++) {
					if (con[i1][i2] > 0)
						r += rg[i1][i2];
				}
			}
			g.drawString("Range : " + Integer.toString(r) + "      ", yoyu_x-30, yoyu_y-50);
		}
					// 点と直線のプロット
		f = new Font("TimesRoman", Font.PLAIN, font);
		g.setFont(f);
		g.setColor(Color.black);
		for (i1 = 0; i1 < n_city; i1++) {
			x1 = yoyu_x + (int)(ritu * (city[i1][0] - min_x));
			y1 = yoyu_y + (int)(ritu * (max_y - city[i1][1]));

			g.fillOval(x1, y1, size, size);
			g.drawString(Integer.toString(i1+1), x1+p, y1-p);

			for (i2 = i1+1; i2 < n_city; i2++) {
				if (con[i1][i2] > 0) {
					x2 = yoyu_x + (int)(ritu * (city[i2][0] - min_x));
					y2 = yoyu_y + (int)(ritu * (max_y - city[i2][1]));
					g.drawLine(x1+p, y1+p, x2+p, y2+p);
				}
			}
		}
	}

	/**************************************/
	/*     nextボタンが押されたときの処理 */
	/**************************************/
	class ClickMouse extends MouseAdapter
	{
		/****************************************/
		/*     マウスがクリックされたときの処理 */
		/****************************************/
		public void mouseClicked(MouseEvent e)
		{
			int i1, sw, pos2, x, xp, y, yp;
							// マウスの位置
			xp = e.getX();
			yp = e.getY();
							// クリックされた都市を決定
			pos2 = -1;
			for (i1 = 0; i1 < n_city && pos2 < 0; i1++) {
				x = yoyu_x + (int)(ritu * (city[i1][0] - min_x));
				y = yoyu_y + (int)(ritu * (max_y - city[i1][1]));
				if (xp > x && xp < x+size && yp > y && yp < y+size)
					pos2 = i1;
			}

			if (pos2 >= 0) {
							// 最初のクリック
				if (pos1 < 0) {
					str  = "Next Position ?";
					pos1 = pos2;
				}
							// ２回目のクリック
				else {
					if (con[pos1][pos2] > 0) {
						con[pos1][pos2] = 0;
						con[pos2][pos1] = 0;
					}
					else {
						con[pos1][pos2] = 1;
						con[pos2][pos1] = 1;
					}
					str  = "";
					pos1 = -1;
				}

				repaint();
			}
		}
	}

	/****************/
	/*     終了処理 */
	/****************/
	class WinEnd extends WindowAdapter
	{
		public void windowClosing(WindowEvent e) {
			tsp.setVisible(false);
		}
	}
}