VRPHeurstics.java

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package vrpheurstics;
import java.util.concurrent.ThreadLocalRandom;

/**
 *
 * @author Gindullin
 */
public class VRPHeurstics {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        int n = 68;

        //double[] x = new double[2*n + 1];
        double[] xulyssus = {38.24, 39.57, 40.56, 36.26, 33.48, 37.56, 38.42, 37.52, 41.23, 41.17, 36.08, 38.47, 38.15, 37.51, 35.49}; //Ulyssus
        double[] xulysses22 = {38.24, 39.57, 40.56, 36.26, 33.48, 37.56, 38.42, 37.52, 41.23, 41.17, 36.08, 38.47, 38.15, 37.51, 35.49, 39.36, 38.09, 36.09, 40.44, 40.33, 40.37}; //ulysses22.tsp
        double[] xbayg29 = {1150, 	630, 	40, 	750, 	750, 	1030, 	1650, 	1490, 	790, 	710, 	840, 	1170, 	970, 	510, 	750, 	1280, 	230, 	460, 	1040, 	590, 	830, 	490, 	1840, 	1260, 	1280, 	490, 	1460, 	1260, 	360}; //bayg29.tsp
        double[] xeil51 = {37, 49, 52, 20, 40, 21, 17, 31, 52, 51, 42, 31, 5, 12, 36, 52, 27, 17, 13, 57, 62, 42, 16, 8, 7, 27, 30, 43, 58, 58, 37, 38, 46, 61, 62, 63, 32, 45, 59, 5, 10, 21, 5, 30, 39, 32, 25, 25, 48, 56, 30}; //eil51.tsp
        double[] xrat99 = {6, 15, 24, 33, 48, 57, 67, 77, 86, 6, 17, 23, 32, 43, 55, 65, 78, 87, 3, 12, 28, 33, 47, 55, 64, 71, 87, 4, 15, 22, 34, 42, 54, 66, 78, 87, 7, 17, 26, 32, 43, 57, 64, 78, 83, 5, 13, 25, 38, 46, 58, 67, 74, 88, 2, 17, 23, 36, 42, 53, 63, 72, 87, 2, 16, 25, 38, 42, 57, 66, 73, 86, 5, 13, 25, 35, 46, 54, 65, 73, 86, 2, 14, 28, 38, 46, 57, 63, 77, 85, 8, 12, 22, 34, 47, 58, 66, 78, 85}; //rat99.tsp
        double[] xgr137 = {71.17, 64.51, 61.13, 58.20, 49.16, 53.33, 51.03, 50.25, 52.07, 49.53, 58.46, 43.39, 45.25, 45.31, 46.49, 44.39, 47.34, 47.36, 47.40, 38.35, 37.48, 34.03, 32.43, 40.46, 33.27, 39.43, 35.05, 31.45, 46.47, 44.59, 41.16, 39.07, 35.28, 32.47, 29.46, 43.02, 41.53, 38.39, 35.08, 29.58, 42.20, 40.26, 39.06, 33.45, 42.21, 40.43, 39.57, 38.54, 30.20, 25.46, 25.05, 28.38, 25.33, 25.40, 22.13, 22.09, 20.40, 19.24, 19.03, 19.20, 16.51, 17.03, 17.59, 20.58, 17.30, 14.38, 13.42, 14.06, 12.09, 9.56, 8.58, 23.08, 22.24, 20.01, 18.00, 18.32, 18.28, 18.28, 14.36, 13.06, 10.39, 12.06, 4.56, 5.50, 6.48, 10.30, 10.40, 10.59, 6.15, 4.36, 3.27, -0.56, -0.13, -1.40, -2.10, -3.46, -8.07, -12.03, -13.31, -16.24, -16.30, -17.48, -19.35, -23.39, -33.27, -36.50, -53.09, -51.42, -38.43, -38.00, -34.50, -34.36, -32.57, -31.24, -32.53, -26.49, -25.16, -30.04, -27.35, -25.25, -23.32, -22.54, -20.23, -19.55, -20.27, -15.35, -16.40, -15.47, -12.59, -8.03, -5.47, -3.43, -5.05, -2.31, -1.27, -3.08, -8.46}; //gr137.tsp
        double[] xgr229 = {68.58, 64.34, 59.55, 59.25, 56.57, 54.43, 54.41, 53.54, 49.50, 50.26, 46.28, 55.45, 56.20, 55.45, 53.12, 51.40, 50.00, 48.27, 44.36, 47.14, 48.44, 46.21, 41.43, 40.11, 40.23, 58.00, 56.51, 67.27, 69.20, 55.00, 55.02, 56.01, 49.50, 43.15, 41.20, 39.40, 38.35, 43.48, 52.16, 47.55, 52.03, 62.13, 64.45, 53.01, 59.34, 50.17, 50.35, 48.27, 46.58, 43.10, 41.01, 38.25, 39.56, 38.43, 39.45, 39.55, 37.55, 37.01, 36.12, 34.44, 33.30, 33.53, 31.57, 32.50, 32.04, 31.46, 24.28, 21.30, 21.27, 15.23, 14.48, 12.45, 14.32, 23.37, 25.18, 25.17, 26.13, 24.38, 29.20, 30.30, 33.21, 35.28, 36.20, 38.05, 37.16, 35.40, 34.19, 30.20, 32.40, 29.36, 30.17, 36.18, 34.20, 31.32, 34.31, 33.36, 31.35, 31.25, 30.11, 30.12, 27.42, 25.22, 24.52, 30.19, 28.40, 26.17, 26.55, 26.28, 25.20, 25.36, 22.32, 23.02, 21.09, 20.30, 18.58, 17.23, 17.42, 15.21, 12.59, 13.05, 10.49, 9.56, 6.56, 27.43, 27.28, 23.43, 22.20, 22.00, 16.47, 18.47, 19.52, 17.58, 21.02, 16.28, 16.04, 10.45, 11.33, 13.45, 5.25, 3.10, 1.17, 3.35, -0.57, -2.55, -6.10, -6.54, -7.48, -7.15, -8.39, -10.10, -3.20, 1.33, 4.56, -0.30, -5.07, 1.29, -3.43, -5.40, 7.04, 10.18, 10.42, 14.35, 22.17, 22.38, 25.03, 29.40, 36.03, 34.15, 30.39, 29.39, 25.05, 23.06, 26.06, 30.36, 32.03, 31.14, 34.48, 36.06, 37.55, 39.08, 39.55, 38.53, 41.48, 45.45, 39.01, 37.33, 35.06, 43.03, 39.43, 38.15, 35.42, 35.10, 36.34, 35.00, 34.40, 34.24, 32.48, 31.36, 26.13, 13.28, -2.32, -4.12, -9.30, -12.28, -31.56, -34.55, -37.49, -42.53, -33.52, -27.28, -19.16, -23.42, -45.52, -43.32, -41.18, -36.52, -21.08, -14.16, -18.08, -22.16, -9.26, -0.32, 11.35, 21.19, 1.52, -9.45, -17.32, -25.04, -27.07}; //gr229.tsp
        double[] xrd400 = {435.84, 602.54, 861.56, 444.22, 796.04, 88.91, 233.57, 476.86, 406.27, 954.57, 593.33, 946.10, 83.07, 861.25, 247.62, 963.23, 125.87, 563.24, 55.26, 691.41, 237.17, 583.45, 404.17, 15.77, 20.08, 196.66, 913.25, 828.34, 49.60, 271.36, 979.15, 489.42, 817.11, 332.77, 278.35, 168.54, 806.14, 445.40, 306.70, 555.49, 156.44, 140.14, 963.24, 460.83, 385.53, 931.46, 279.89, 331.28, 33.54, 511.53, 232.87, 870.56, 126.31, 25.72, 550.99, 421.55, 699.40, 30.61, 486.63, 547.89, 764.19, 489.34, 908.76, 195.23, 171.85, 599.16, 132.52, 327.21, 267.93, 792.92, 156.99, 186.10, 746.00, 672.67, 795.06, 298.83, 91.60, 917.90, 370.27, 789.21, 800.35, 748.36, 486.98, 148.74, 231.98, 972.91, 40.56, 192.47, 24.04, 316.69, 494.94, 525.12, 835.67, 775.21, 109.48, 653.01, 628.29, 1.95, 730.64, 580.37, 377.45, 258.13, 659.30, 700.98, 801.21, 755.12, 168.35, 607.71, 569.79, 505.77, 692.79, 615.26, 433.07, 227.00, 326.41, 756.36, 175.19, 207.26, 127.31, 245.18, 368.49, 618.45, 284.62, 347.49, 942.05, 923.03, 153.76, 476.33, 232.09, 439.63, 959.40, 659.33, 475.22, 734.71, 844.59, 10.25, 359.09, 901.10, 607.21, 682.39, 840.93, 449.96, 725.65, 882.70, 429.87, 980.88, 578.12, 541.69, 509.21, 875.59, 101.22, 485.89, 134.00, 167.24, 156.37, 267.98, 476.48, 456.95, 217.25, 165.47, 381.61, 310.77, 2.20, 135.32, 257.71, 678.11, 176.01, 560.39, 416.78, 852.35, 850.69, 745.77, 104.73, 64.34, 417.21, 884.47, 868.71, 262.00, 669.76, 420.18, 424.97, 615.07, 967.47, 180.64, 153.90, 138.31, 23.88, 701.02, 951.54, 190.12, 347.58, 331.09, 547.39, 776.79, 756.59, 172.31, 85.71, 904.88, 87.54, 21.97, 417.30, 205.64, 486.74, 372.18, 117.94, 295.53, 879.34, 889.91, 636.98, 382.49, 134.60, 759.96, 44.51, 244.59, 642.57, 228.19, 645.77, 881.96, 680.57, 812.00, 963.48, 312.68, 853.96, 518.36, 272.48, 762.21, 648.78, 783.67, 399.48, 32.50, 814.21, 291.05, 607.01, 92.75, 769.07, 175.86, 344.66, 227.18, 491.15, 25.52, 789.06, 980.73, 58.18, 195.26, 543.71, 557.17, 256.51, 805.44, 462.04, 818.21, 415.46, 203.29, 325.90, 512.47, 826.91, 374.11, 599.16, 327.35, 360.03, 809.91, 260.67, 934.25, 176.02, 606.97, 667.65, 852.86, 746.32, 93.56, 818.77, 746.62, 231.08, 683.55, 431.01, 709.83, 452.18, 384.81, 886.34, 52.58, 152.73, 808.89, 775.35, 178.09, 988.74, 114.26, 236.13, 314.34, 273.60, 50.00, 6.43, 540.01, 786.06, 995.16, 509.98, 890.36, 304.47, 473.92, 868.56, 91.73, 616.79, 414.13, 236.21, 974.77, 732.09, 334.19, 561.25, 33.01, 451.64, 197.29, 236.34, 747.87, 430.78, 21.82, 344.64, 754.79, 257.18, 233.29, 109.64, 818.50, 438.96, 344.94, 920.63, 950.47, 123.80, 826.84, 967.72, 763.86, 477.09, 189.04, 500.42, 807.78, 6.14, 680.53, 752.46, 740.57, 494.05, 225.45, 782.19, 559.93, 463.40, 99.61, 257.62, 42.89, 172.91, 483.21, 537.14, 2.99, 286.89, 34.46, 382.17, 407.05, 957.66, 534.25, 891.08, 609.91, 800.51, 6.59, 122.62, 517.93, 235.39, 603.56, 910.37, 498.33, 548.67, 779.11, 582.10, 214.74, 560.44, 693.67, 90.50, 760.50, 626.52, 995.85, 918.95, 989.58, 377.69, 961.42, 825.41, 827.46, 35.78, 620.15, 109.52, 738.93, 274.22, 82.54, 592.71, 724.78, 778.13, 885.71, 26.89, 741.31, 165.76, 256.23, 927.39, 524.93, 72.19, 367.23, 349.22, 127.12, 587.64}; //rd400.tsp
        double[] xch130 = {334.5909245845, 397.6446634067, 503.8741827107, 444.0479403502, 311.6137146746, 662.8551011379, 40.0979030612, 526.8941409181, 209.1887938487, 683.2674131973, 280.7494438748, 252.7493090080, 698.7850451923, 678.7574678104, 220.0041131179, 355.1528556851, 296.9724227786, 504.5154071733, 224.1079496785, 470.6801296968, 554.2530513223, 567.6332684419, 599.0532671093, 240.5232959211, 32.0825972787, 91.0538736891, 248.2179894723, 488.8909044347, 206.0467939820, 575.8409415632, 282.6089948164, 27.6581484868, 568.5737309870, 269.4638933331, 417.8004856811, 32.1680938737, 561.4775136009, 342.9482167470, 399.6752075383, 571.7371050025, 370.7559842751, 509.7093253204, 177.0206999750, 526.1674198605, 316.5725171854, 469.2908100279, 572.7630641427, 29.5176994283, 454.0082936692, 416.1546762271, 535.2514330806, 265.4455533675, 478.0542110167, 370.4781203413, 598.3479202004, 201.1521139175, 193.6925360026, 448.5792598859, 603.2853485624, 543.0102490781, 214.5750793346, 426.3501451825, 89.0447037063, 84.4920100219, 220.0468614154, 688.4613313444, 687.2857531630, 75.4934933967, 63.4170993511, 97.9363495877, 399.5255884970, 456.3167017346, 319.8855102422, 295.9250894897, 288.4868857235, 268.3951858954, 140.4709056068, 689.8079027159, 280.5784506848, 453.3884433554, 213.5704943432, 133.6953004520, 521.1658690522, 30.2657946347, 657.0199585283, 6.9252241961, 252.4286967767, 42.8551682504, 145.8999393902, 638.4885715591, 489.2756391122, 361.2231139311, 519.9475425732, 129.3349741063, 259.7172815016, 676.3421890013, 84.5133841706, 77.7164048671, 335.9802442534, 264.3554717810, 51.6826916855, 692.1376849300, 169.2191356800, 194.0131482339, 415.1928395332, 415.0432204919, 169.8389859939, 525.0987124228, 238.6851191283, 116.2112467718, 16.9283258126, 434.3440768162, 40.5253860363, 530.4849979086, 484.3595848990, 263.6501248722, 450.2891917862, 441.7822805823, 24.2169105375, 503.7886861157, 635.5389390312, 614.5922732529, 21.7161351334, 143.8266469611, 637.7191022040, 566.5645610042, 196.6849168280, 384.9270448985, 178.1107815614, 403.2874386776}; //ch130.tsp
        double[] xgil262 = {-99, -59, 0, -17, -69, 31, 5, -12, -64, -12, -18, -77, -53, 83, 24, 17, 42, -65, -47, 85, -35, 54, 64, 55, 17, -61, -61, 17, 79, -62, -90, 52, -54, 8, 37, -83, 35, 7, 12, 57, 92, -3, -7, 42, 77, 59, 25, 69, -82, 74, 69, 29, -97, -58, 28, 7, -28, -76, 41, 92, -84, -12, 51, -37, -97, 14, 60, -63, -18, -46, -86, -43, -44, -3, 36, -30, 79, 51, -61, 6, -19, -20, -81, 7, 52, 83, -7, 82, -70, -83, 71, 85, 66, 78, 9, -36, 66, 92, -46, -30, -42, 20, 15, 1, 64, -96, 93, -40, 86, 91, 62, -24, 11, -53, -28, 7, 95, -3, 53, 58, -83, -1, -4, -82, -43, 6, 70, 68, -94, -94, -21, 64, -70, 88, 2, 33, -70, -38, -80, -5, 8, -61, 76, 49, -30, 1, 77, -58, 82, -80, 81, 39, -67, -25, -44, 32, -17, 93, 99, 10, 63, 38, -28, -2, 38, -42, -67, 19, 40, -61, 43, -18, -69, 75, 31, 25, -16, 91, 60, 49, 42, 16, -78, 53, -46, -25, 69, 0, -84, -16, -63, 51, -39, 5, -55, 70, 0, -45, 38, 50, 59, -73, -29, -47, -88, -88, -46, 26, -39, 92, -80, 93, -20, -22, -4, 54, -70, 54, 29, -87, -96, 49, -5, -26, -11, 40, 82, -92, -93, -66, -72, -57, 23, -56, -19, 63, -13, -19, 44, 98, -16, 3, 26, -38, 70, 17, 96, -77, -14, -33, 33, 70, -50, -50, 75, 0, -75, 0, 40, 40, -60, -60}; //gil262.tsp
        double[] xpa561 = {678, 733, 748, 772, 804, 804, 816, 789, 769, 743, 776, 830, 882, 927, 927, 882, 907, 842, 860, 825, 890, 880, 900, 927, 930, 910, 932, 913, 893, 870, 910, 767, 806, 830, 825, 817, 801, 762, 726, 748, 791, 703, 716, 733, 776, 753, 723, 704, 709, 724, 756, 774, 764, 746, 726, 726, 693, 809, 821, 839, 854, 869, 923, 912, 889, 852, 834, 827, 792, 776, 751, 709, 728, 884, 857, 817, 842, 809, 845, 791, 797, 835, 819, 882, 864, 849, 834, 801, 777, 791, 774, 762, 726, 713, 683, 696, 701, 703, 749, 774, 781, 724, 728, 744, 741, 607, 603, 590, 580, 600, 577, 544, 535, 603, 563, 547, 529, 612, 592, 542, 519, 603, 585, 563, 512, 617, 600, 607, 597, 580, 563, 549, 524, 476, 510, 492, 432, 457, 482, 459, 447, 419, 403, 384, 447, 408, 374, 378, 398, 411, 427, 383, 575, 590, 554, 547, 537, 525, 507, 507, 497, 524, 517, 504, 502, 489, 467, 437, 467, 447, 432, 685, 661, 673, 690, 646, 678, 658, 640, 651, 678, 633, 651, 633, 615, 592, 570, 547, 612, 572, 524, 530, 534, 549, 567, 552, 532, 500, 517, 602, 507, 573, 507, 550, 660, 683, 701, 685, 665, 623, 641, 668, 701, 685, 457, 444, 427, 423, 491, 464, 439, 394, 399, 432, 456, 479, 466, 359, 346, 336, 316, 296, 275, 277, 288, 318, 296, 313, 340, 363, 388, 381, 343, 361, 363, 345, 363, 303, 282, 268, 252, 238, 492, 471, 439, 411, 413, 456, 476, 431, 427, 396, 373, 350, 363, 323, 325, 290, 260, 260, 277, 265, 298, 308, 328, 325, 313, 290, 268, 255, 237, 187, 159, 131, 139, 160, 187, 245, 243, 242, 252, 273, 265, 248, 233, 290, 290, 268, 243, 224, 233, 265, 298, 291, 303, 265, 248, 227, 255, 378, 335, 315, 306, 345, 366, 388, 406, 409, 374, 364, 320, 333, 363, 635, 615, 610, 598, 550, 554, 580, 631, 583, 607, 555, 547, 583, 563, 534, 535, 514, 514, 495, 673, 651, 650, 643, 675, 675, 643, 656, 615, 636, 598, 622, 598, 560, 563, 587, 555, 520, 504, 525, 494, 457, 457, 431, 399, 411, 419, 363, 378, 359, 315, 333, 263, 285, 233, 169, 169, 476, 426, 426, 376, 398, 330, 341, 293, 272, 306, 316, 273, 248, 207, 204, 172, 200, 170, 529, 527, 524, 504, 510, 510, 494, 491, 471, 464, 454, 442, 421, 411, 432, 419, 399, 386, 378, 383, 529, 510, 529, 515, 510, 491, 474, 477, 494, 495, 482, 479, 461, 454, 442, 446, 464, 411, 409, 363, 346, 351, 363, 346, 331, 313, 308, 308, 293, 270, 278, 252, 230, 240, 250, 180, 217, 209, 160, 182, 156, 320, 305, 291, 272, 278, 257, 238, 250, 233, 235, 207, 214, 214, 195, 177, 177, 154, 177, 174, 149, 151, 487, 491, 500, 481, 469, 457, 442, 434, 466, 464, 444, 418, 403, 418, 399, 401, 384, 384, 383, 366, 368, 429, 403, 393, 363, 363, 363, 333, 311, 325, 315, 340, 350, 341, 321, 353, 340, 335, 305, 318, 300, 298, 285, 277, 257, 255, 233, 215, 224, 238, 255, 210, 240, 233, 230, 215, 190, 187, 199, 192, 164, 141, 268, 268, 243, 243, 222, 225, 190, 190, 207, 162, 164, 162, 149, 129, 129, 104, 104, 69, 34, 34}; //pa561.tsp
        double[] xgr666 = {90 ,71.17 ,64.51 ,61.13 ,58.2 ,49.16 ,53.33 ,51.03 ,50.25 ,52.07 ,49.53 ,58.46 ,43.39 ,45.25 ,45.31 ,46.49 ,44.39 ,47.34 ,47.36 ,47.4 ,38.35 ,37.48 ,34.03 ,32.43 ,40.46 ,33.27 ,39.43 ,35.05 ,31.45 ,46.47 ,44.59 ,41.16 ,39.07 ,35.28 ,32.47 ,29.46 ,43.02 ,41.53 ,38.39 ,35.08 ,29.58 ,42.2 ,40.26 ,39.06 ,33.45 ,42.21 ,40.43 ,39.57 ,38.54 ,30.2 ,25.46 ,25.05 ,28.38 ,25.33 ,25.4 ,22.13 ,22.09 ,20.4 ,19.24 ,19.03 ,19.2 ,16.51 ,17.03 ,17.59 ,20.58 ,17.3 ,14.38 ,13.42 ,14.06 ,12.09 ,9.56 ,8.58 ,23.08 ,22.24 ,20.01 ,18 ,18.32 ,18.28 ,18.28 ,14.36 ,13.06 ,10.39 ,12.06 ,4.56 ,5.5 ,6.48 ,10.3 ,10.4 ,10.59 ,6.15 ,4.36 ,3.27 ,-0.56 ,-0.13 ,-1.4 ,-2.1 ,-3.46 ,-8.07 ,-12.03 ,-13.31 ,-16.24 ,-16.3 ,-17.48 ,-19.35 ,-23.39 ,-33.27 ,-36.5 ,-53.09 ,-51.42 ,-38.43 ,-38 ,-34.5 ,-34.36 ,-32.57 ,-31.24 ,-32.53 ,-26.49 ,-25.16 ,-30.04 ,-27.35 ,-25.25 ,-23.32 ,-22.54 ,-20.23 ,-19.55 ,-20.27 ,-15.35 ,-16.4 ,-15.47 ,-12.59 ,-8.03 ,-5.47 ,-3.43 ,-5.05 ,-2.31 ,-1.27 ,-3.08 ,-8.46 ,14.55 ,28.06 ,32.38 ,31.38 ,33.39 ,34.02 ,34.05 ,35.48 ,35.43 ,36.47 ,22.56 ,36.22 ,36.48 ,34.44 ,32.54 ,32.07 ,31.12 ,31.16 ,29.58 ,30.03 ,24.05 ,19.37 ,15.36 ,13.11 ,13.38 ,15.2 ,9 ,11.36 ,18.06 ,14.4 ,13.28 ,11.51 ,16.46 ,12.39 ,10.23 ,9.31 ,8.3 ,6.18 ,5.19 ,6.41 ,5.33 ,6.08 ,6.29 ,12.22 ,13.31 ,12 ,11.51 ,12.07 ,6.27 ,6.27 ,0.2 ,3.45 ,3.52 ,4.22 ,0.23 ,-4.16 ,-4.18 ,0.04 ,-5.54 ,0.3 ,-3.23 ,-1.57 ,0.19 ,-1.17 ,2.01 ,-4.03 ,-6.1 ,-6.48 ,-8.48 ,-12.44 ,-11.4 ,-12.49 ,-15.25 ,-20.09 ,-17.5 ,-15.47 ,-19.49 ,-25.58 ,-15.57 ,-37.15 ,-22.59 ,-22.34 ,-26.38 ,-24.45 ,-25.45 ,-26.15 ,-29.12 ,-29.55 ,-33 ,-33.58 ,-33.55 ,-23.21 ,-18.55 ,-12.16 ,-20.1 ,-4.38 ,37.44 ,38.43 ,41.11 ,37.23 ,36.32 ,36.43 ,37.13 ,37.53 ,38.21 ,39.28 ,41.23 ,41.38 ,40.24 ,41.39 ,43.15 ,43.22 ,38.54 ,39.34 ,42.3 ,44.5 ,43.36 ,43.18 ,43.42 ,43.42 ,42.42 ,45.5 ,45.26 ,45.45 ,45.1 ,48.24 ,48.05 ,47.13 ,47.23 ,49.3 ,48.52 ,49.15 ,47.19 ,48.41 ,48.35 ,49.36 ,50.38 ,50.5 ,50.38 ,51.03 ,51.13 ,51.26 ,51.55 ,52.22 ,52.05 ,53.13 ,50.23 ,50.43 ,50.5 ,51.29 ,51.27 ,51.3 ,52.3 ,53.25 ,53.3 ,53.23 ,53.5 ,54.59 ,55.57 ,55.53 ,56.28 ,57.1 ,60.09 ,62.01 ,51.54 ,52.4 ,53.2 ,54.35 ,55 ,64.09 ,64.11 ,76.34 ,70.4 ,68.26 ,65.01 ,61.3 ,60.27 ,60.1 ,63.25 ,60.23 ,58.58 ,59.55 ,57.43 ,55.36 ,58.25 ,59.2 ,57.38 ,56.09 ,55.24 ,55.4 ,53.04 ,53.33 ,54.2 ,54.05 ,51.57 ,52.24 ,52.07 ,52.31 ,50.47 ,50.44 ,50.56 ,51.12 ,51.17 ,51.28 ,51.28 ,51.32 ,51.31 ,51.19 ,50.58 ,51.29 ,51.19 ,50.5 ,51.03 ,49.14 ,50.07 ,49.25 ,49.48 ,49.27 ,49.03 ,48.46 ,49.01 ,48.08 ,46.12 ,46.31 ,46.57 ,47.33 ,47.23 ,47.16 ,47.48 ,48.18 ,48.13 ,47.05 ,45.03 ,45.28 ,45.27 ,45.27 ,45.4 ,44.25 ,44.29 ,43.46 ,43.55 ,39.2 ,41.54 ,40.51 ,41.27 ,41.07 ,40.28 ,38.11 ,37.3 ,38.07 ,35.54 ,53.24 ,54.23 ,53.08 ,52.25 ,51.46 ,52.15 ,53.09 ,51.06 ,50.16 ,50.03 ,51.15 ,49.45 ,50.05 ,49.5 ,49.12 ,48.09 ,48.43 ,47.3 ,47.32 ,46.05 ,46.15 ,45.45 ,46.47 ,47.1 ,45.48 ,45.39 ,44.26 ,44.11 ,46.03 ,45.2 ,45.48 ,43.31 ,43.52 ,44.5 ,42.38 ,41.59 ,41.2 ,42.41 ,42.09 ,43.13 ,42.3 ,39.36 ,40.38 ,38.15 ,37.58 ,35.2 ,35.1 ,68.58 ,64.34 ,59.55 ,59.25 ,56.57 ,54.43 ,54.41 ,53.54 ,49.5 ,50.26 ,46.28 ,55.45 ,56.2 ,55.45 ,53.12 ,51.4 ,50 ,48.27 ,44.36 ,47.14 ,48.44 ,46.21 ,41.43 ,40.11 ,40.23 ,58 ,56.51 ,67.27 ,69.2 ,55 ,55.02 ,56.01 ,49.5 ,43.15 ,41.2 ,39.4 ,38.35 ,43.48 ,52.16 ,47.55 ,52.03 ,62.13 ,64.45 ,53.01 ,59.34 ,50.17 ,50.35 ,48.27 ,46.58 ,43.1 ,41.01 ,38.25 ,39.56 ,38.43 ,39.45 ,39.55 ,37.55 ,37.01 ,36.12 ,34.44 ,33.3 ,33.53 ,31.57 ,32.5 ,32.04 ,31.46 ,24.28 ,21.3 ,21.27 ,15.23 ,14.48 ,12.45 ,14.32 ,23.37 ,25.18 ,25.17 ,26.13 ,24.38 ,29.2 ,30.3 ,33.21 ,35.28 ,36.2 ,38.05 ,37.16 ,35.4 ,34.19 ,30.2 ,32.4 ,29.36 ,30.17 ,36.18 ,34.2 ,31.32 ,34.31 ,33.36 ,31.35 ,31.25 ,30.11 ,30.12 ,27.42 ,25.22 ,24.52 ,30.19 ,28.4 ,26.17 ,26.55 ,26.28 ,25.2 ,25.36 ,22.32 ,23.02 ,21.09 ,20.3 ,18.58 ,17.23 ,17.42 ,15.21 ,12.59 ,13.05 ,10.49 ,9.56 ,6.56 ,27.43 ,27.28 ,23.43 ,22.2 ,22 ,16.47 ,18.47 ,19.52 ,17.58 ,21.02 ,16.28 ,16.04 ,10.45 ,11.33 ,13.45 ,5.25 ,3.1 ,1.17 ,3.35 ,-0.57 ,-2.55 ,-6.1 ,-6.54 ,-7.48 ,-7.15 ,-8.39 ,-10.1 ,-3.2 ,1.33 ,4.56 ,-0.3 ,-5.07 ,1.29 ,-3.43 ,-5.4 ,7.04 ,10.18 ,10.42 ,14.35 ,22.17 ,22.38 ,25.03 ,29.4 ,36.03 ,34.15 ,30.39 ,29.39 ,25.05 ,23.06 ,26.06 ,30.36 ,32.03 ,31.14 ,34.48 ,36.06 ,37.55 ,39.08 ,39.55 ,38.53 ,41.48 ,45.45 ,39.01 ,37.33 ,35.06 ,43.03 ,39.43 ,38.15 ,35.42 ,35.1 ,36.34 ,35 ,34.4 ,34.24 ,32.48 ,31.36 ,26.13 ,13.28 ,-2.32 ,-4.12 ,-9.3 ,-12.28 ,-31.56 ,-34.55 ,-37.49 ,-42.53 ,-33.52 ,-27.28 ,-19.16 ,-23.42 ,-45.52 ,-43.32 ,-41.18 ,-36.52 ,-21.08 ,-14.16 ,-18.08 ,-22.16 ,-9.26 ,-0.32 ,11.35 ,21.19 ,1.52 ,-9.45 ,-17.32 ,-25.04 ,-27.07 ,-90}; //gr666.tsp
        //double[] y = new double[2*n + 1];
        double[] yulyssus = {20.42, 26.15, 25.32, 23.12, 10.54, 12.19, 13.11, 20.44, 9.10, 13.05, -5.21, 15.13, 15.35, 15.17, 14.32}; //Ulyssus
        double[] yulysses22 = {20.42, 26.15, 25.32, 23.12, 10.54, 12.19, 13.11, 20.44, 9.1, 13.05, -5.21, 15.13, 15.35, 15.17, 14.32, 19.56, 24.36, 23, 13.57, 14.15, 14.23}; //ulysses22.tsp
        double[] ybayg29 = {1760, 	1660, 	2090, 	1100, 	2030, 	2070, 	650, 	1630, 	2260, 	1310, 	550, 	2300, 	1340, 	700, 	900, 	1200, 	590, 	860, 	950, 	1390, 	1770, 	500, 	1240, 	1500, 	790, 	2130, 	1420, 	1910, 	1980}; //bayg29.tsp
        double[] yeil51 = {52, 49, 64, 26, 30, 47, 63, 62, 33, 21, 41, 32, 25, 42, 16, 41, 23, 33, 13, 58, 42, 57, 57, 52, 38, 68, 48, 67, 48, 27, 69, 46, 10, 33, 63, 69, 22, 35, 15, 6, 17, 10, 64, 15, 10, 39, 32, 55, 28, 37, 40}; //eil51.tsp
        double[] yrat99 = {4, 15, 18, 12, 12, 14, 10, 10, 15, 21, 26, 25, 35, 23, 35, 36, 39, 35, 53, 44, 53, 49, 46, 52, 50, 57, 57, 72, 78, 70, 71, 79, 77, 79, 67, 73, 81, 95, 98, 97, 88, 89, 85, 83, 98, 109, 111, 102, 119, 107, 110, 110, 113, 110, 124, 134, 129, 131, 137, 123, 135, 134, 129, 146, 147, 153, 155, 158, 154, 151, 151, 149, 177, 162, 169, 177, 172, 166, 174, 161, 162, 195, 196, 189, 187, 195, 194, 188, 193, 194, 211, 217, 210, 216, 203, 213, 206, 210, 204}; //rat99.tsp
        double[] ygr137 = {-156.47, -147.43, -149.53, -134.27, -123.07, -113.28, -114.05, -104.39, -106.38, -97.09, -94.1, -79.23, -75.42, -73.34, -71.14, -63.36, -52.43, -122.2, -117.23, -121.3, -122.24, -118.15, -117.09, -111.53, -112.05, -105.01, -106.4, -106.29, -92.06, -93.13, -95.57, -94.39, -97.32, -96.48, -95.22, -87.55, -87.38, -90.25, -90.03, -90.07, -83.03, -80, -84.31, -84.23, -71.04, -74.01, -75.07, -77.01, -81.4, -80.12, -77.21, -106.05, -103.26, -100.19, -97.51, -100.59, -103.2, -99.09, -98.12, -96.4, -99.55, -96.43, -92.55, -89.37, -88.12, -90.31, -89.12, -87.13, -86.17, -84.05, -79.32, -82.22, -79.58, -75.49, -76.48, -72.2, -69.54, -66.07, -61.05, -59.37, -61.31, -68.56, -52.2, -55.1, -58.1, -66.56, -71.37, -74.48, -75.35, -74.05, -76.31, -91.01, -78.3, -78.38, -79.5, -73.15, -79.02, -77.03, -71.59, -71.33, -68.09, -63.1, -65.45, -70.24, -70.4, -73.03, -70.55, -57.51, -62.17, -57.33, -56.12, -58.27, -60.4, -64.11, -68.49, -65.13, -57.4, -51.11, -48.34, -49.15, -46.37, -43.14, -43.3, -43.56, -54.37, -56.05, -49.16, -47.55, -38.31, -34.54, -35.13, -38.3, -42.49, -44.16, -48.29, -60.01, -63.54}; //gr137.tsp
        double[] ygr229 = {33.05, 40.32, 30.15, 24.45, 24.06, 20.30, 25.19, 27.34, 24.00, 30.31, 30.44, 37.35, 44.00, 49.08, 50.09, 39.10, 36.15, 34.59, 33.32, 39.42, 44.25, 48.03, 44.49, 44.30, 49.51, 56.15, 60.36, 63.58, 88.06, 73.24, 82.55, 92.50, 73.10, 76.57, 69.18, 66.48, 68.48, 87.35, 104.20, 106.53, 113.30, 129.49, 177.29, 158.39, 150.48, 127.32, 137.02, 135.06, 142.42, 131.56, 28.58, 27.09, 32.52, 35.30, 37.02, 41.17, 40.14, 35.18, 37.10, 36.43, 36.18, 35.30, 35.56, 35.00, 34.46, 35.14, 39.36, 39.12, 39.49, 44.12, 42.57, 45.12, 49.08, 58.35, 55.18, 51.32, 50.35, 46.43, 47.59, 47.47, 44.25, 44.28, 43.08, 46.18, 49.36, 51.26, 47.04, 48.16, 51.38, 52.32, 57.05, 59.36, 62.12, 65.30, 69.12, 73.04, 74.18, 73.05, 71.29, 67.00, 68.52, 68.22, 67.03, 78.02, 77.13, 73.02, 75.49, 80.21, 83.00, 85.07, 88.22, 72.37, 79.06, 85.50, 72.50, 78.29, 83.18, 75.10, 77.35, 80.17, 78.41, 78.07, 79.51, 85.19, 89.39, 90.25, 91.50, 96.05, 96.10, 98.59, 102.08, 102.36, 105.51, 107.36, 108.13, 106.40, 104.55, 100.31, 100.20, 101.42, 103.51, 98.40, 100.21, 104.45, 106.48, 107.36, 110.22, 112.45, 115.13, 123.35, 114.35, 110.20, 114.55, 117.09, 119.24, 124.51, 128.12, 132.45, 125.36, 123.54, 122.34, 121.00, 114.09, 120.17, 121.30, 91.09, 103.41, 108.52, 104.04, 106.34, 102.40, 113.16, 119.17, 114.17, 118.47, 121.28, 113.39, 120.19, 112.30, 117.12, 116.25, 121.35, 123.27, 126.41, 125.45, 126.58, 129.03, 141.21, 140.07, 140.53, 139.46, 136.55, 136.39, 135.45, 135.30, 132.27, 129.55, 130.33, 127.40, 144.47, 140.42, 152.12, 147.10, 130.50, 115.50, 138.35, 144.58, 147.19, 151.13, 153.02, 146.48, 133.53, 170.30, 172.38, 174.47, 174.46, -175.12, -170.42, 178.25, 166.27, 159.57, 166.55, 165.23, -157.52, -157.20, -139.00, -149.34, -130.06, -109.22}; //gr229.tsp
        double[] yrd400 = {587.52, 801.70, 954.02, 553.30, 796.52, 838.95, 850.80, 203.98, 601.84, 785.05, 968.64, 433.00, 601.49, 754.12, 698.64, 965.82, 536.99, 20.74, 619.09, 576.65, 707.30, 609.20, 942.22, 614.64, 62.90, 613.86, 428.90, 584.11, 40.61, 736.90, 716.97, 957.95, 281.12, 466.52, 945.62, 974.81, 537.75, 306.86, 552.63, 359.32, 179.00, 704.08, 442.63, 255.50, 487.85, 198.15, 896.02, 923.48, 889.86, 60.41, 327.74, 747.86, 27.08, 384.71, 317.71, 669.86, 641.83, 881.32, 987.92, 870.17, 227.84, 885.47, 483.32, 821.48, 111.94, 587.50, 507.63, 868.80, 788.35, 136.52, 187.48, 903.49, 818.74, 141.52, 496.70, 796.84, 378.02, 105.23, 274.58, 738.17, 158.59, 537.03, 88.59, 95.11, 10.13, 220.42, 259.59, 292.71, 509.81, 311.82, 163.27, 681.26, 882.71, 181.05, 27.35, 671.87, 197.06, 712.34, 447.00, 933.47, 863.51, 251.37, 693.42, 439.31, 327.66, 581.70, 774.79, 673.20, 359.95, 795.09, 475.06, 416.03, 854.11, 149.20, 615.68, 997.07, 551.63, 753.08, 986.13, 595.85, 322.47, 808.45, 905.82, 932.54, 733.58, 410.17, 231.00, 253.18, 588.07, 819.34, 382.33, 989.17, 422.92, 76.17, 856.24, 829.53, 688.83, 207.15, 778.84, 84.71, 757.36, 883.52, 402.26, 149.99, 229.25, 821.98, 545.10, 818.38, 164.05, 251.23, 820.45, 5.48, 228.87, 943.59, 445.89, 69.02, 711.84, 809.26, 20.11, 811.81, 457.55, 220.82, 25.85, 579.26, 332.93, 546.50, 611.72, 331.02, 521.54, 420.31, 321.30, 57.08, 588.78, 87.02, 194.19, 559.13, 180.07, 425.60, 662.31, 34.43, 239.97, 4.82, 235.62, 963.28, 253.90, 544.78, 240.30, 43.45, 792.33, 9.77, 997.52, 8.83, 204.85, 291.29, 917.90, 772.75, 33.67, 126.22, 389.28, 102.51, 581.20, 477.22, 625.48, 77.92, 480.47, 923.19, 967.33, 107.70, 852.55, 96.17, 416.19, 814.02, 940.86, 473.99, 589.53, 537.55, 36.62, 436.36, 156.19, 466.21, 584.97, 611.34, 621.64, 989.63, 202.43, 751.46, 603.79, 742.08, 192.27, 938.75, 436.49, 292.05, 13.61, 433.97, 182.92, 408.86, 388.19, 343.60, 328.61, 669.80, 180.38, 735.09, 207.45, 304.48, 996.06, 378.51, 606.64, 372.79, 417.06, 629.89, 823.74, 280.22, 907.59, 906.53, 802.72, 494.36, 619.97, 384.37, 175.04, 758.32, 213.38, 685.02, 365.20, 355.07, 810.28, 824.65, 56.04, 531.10, 606.90, 491.77, 960.55, 930.49, 685.79, 561.08, 663.38, 812.57, 4.94, 271.00, 951.55, 763.53, 780.35, 519.55, 256.46, 377.41, 494.21, 438.08, 173.03, 742.73, 353.95, 528.66, 432.58, 77.75, 834.34, 307.26, 535.69, 22.31, 484.80, 661.36, 748.51, 748.20, 683.44, 171.80, 320.50, 594.83, 14.05, 545.76, 797.97, 1.99, 400.12, 360.27, 816.48, 256.85, 230.39, 929.34, 178.95, 789.18, 555.18, 388.54, 136.90, 837.52, 460.34, 33.98, 911.15, 234.88, 166.52, 558.64, 834.77, 621.27, 885.26, 879.35, 122.62, 979.54, 173.08, 359.87, 199.61, 556.17, 687.57, 171.43, 711.70, 192.35, 814.54, 926.49, 173.23, 814.33, 893.85, 973.27, 436.08, 282.05, 228.74, 857.82, 25.53, 449.90, 771.61, 714.95, 368.53, 197.00, 436.92, 649.46, 41.31, 723.74, 948.62, 926.57, 952.85, 99.02, 75.61, 82.19, 622.94, 555.59, 16.80, 411.84, 526.72, 234.58, 876.68, 47.32, 314.41, 413.03, 709.36, 580.48, 990.37, 281.82, 120.78, 820.77, 258.43, 643.57, 764.17, 471.17, 902.45, 666.38, 163.88, 972.94, 712.31, 126.55, 899.53, 53.72, 423.80, 863.35, 799.33, 42.91, 139.57}; //rd400.tsp
        double[] ych130 = {161.7809319139, 262.8165330708, 172.8741151168, 384.6491809647, 2.0091699828, 549.2301263653, 187.2375430791, 215.7079092185, 691.0262291948, 414.2096286906, 5.9206392047, 535.7430385019, 348.4413729766, 410.7256424438, 409.1225812873, 76.3912076444, 313.1312792361, 240.8866564499, 358.4872228907, 309.6259188406, 279.4242466521, 352.7162027273, 361.0948690386, 430.6036007844, 345.8551009775, 148.7213270256, 343.9528017384, 3.6122311393, 437.7639406167, 141.9670960195, 329.4183805862, 424.7684581747, 287.0975660546, 295.9464636385, 341.2596589955, 448.8998721172, 357.3543930067, 492.3321423839, 156.8435035519, 375.7575350833, 151.9060751898, 435.7975189314, 295.6044772584, 409.4859418161, 65.6400108214, 281.9891445025, 373.3208821255, 330.0382309000, 537.2178547659, 227.6133100741, 471.0648643744, 684.9987192464, 509.6452028741, 332.5390063041, 446.8693279856, 649.0260268945, 680.2322840744, 532.7934059740, 134.4006473609, 481.5168231148, 43.6460117543, 61.7285415996, 277.1158385868, 31.8474816424, 623.0778103080, 0.4702312726, 373.5346236130, 312.9175377486, 23.7039309674, 211.0910930878, 170.8221968365, 597.1937161677, 626.8396604886, 664.6291554845, 667.7284070537, 52.9010181645, 513.5566720960, 167.5947003748, 458.7533546925, 282.9082328989, 525.8681817779, 677.1757808026, 132.8617086506, 450.0754502986, 39.7772908299, 23.8749241575, 535.1659364856, 63.8232081774, 399.5255884970, 62.6262558472, 665.3131282446, 564.2347787901, 347.9711417040, 435.6692740389, 454.6495181318, 371.0979706551, 183.3260738572, 354.3833863300, 660.6321896676, 377.5743377274, 676.0429509187, 543.8010925819, 547.8194325476, 263.4791316822, 78.9133571973, 479.0801701569, 245.6103433244, 213.5063718969, 33.4932910965, 363.5742702940, 656.5711014044, 92.6996831431, 424.6829615797, 183.8390534273, 49.2460387276, 426.5852608187, 126.3853415784, 299.7724362653, 500.3474481664, 514.6895019799, 200.9811207275, 418.8691931188, 660.9741760476, 92.6996831431, 54.2048412384, 199.9551615873, 221.8209157619, 87.4630166986, 104.6905805938, 205.8971749407}; //ch130.tsp
        double[] ygil262 = {-97, 50, 14, -66, -19, 12, -41, 10, 70, 85, 64, -16, 88, -24, 41, 21, 96, 0, -26, 36, -54, -21, -17, 89, -25, 66, 26, -72, 38, -2, -68, 66, -50, -84, -90, 49, -1, 59, 48, 95, 28, 97, 52, -15, -43, -49, 91, -19, -14, -70, 59, 33, 9, 9, 93, 73, 73, 55, 42, 40, -29, 42, -45, 46, 35, 89, 58, -75, 34, -82, -79, -30, 7, -20, 41, -94, -62, 70, -26, 94, -62, 51, 37, 31, 12, -91, -92, -74, 85, -30, -61, 11, -48, -87, -79, 4, 39, -17, -79, -63, 63, 42, 98, -17, 20, 85, -29, -84, 35, 36, -8, 4, 96, 62, -71, -4, -9, 17, -90, -19, 84, 49, 17, -3, 47, -6, 99, -29, -30, -20, 77, 37, -19, 65, 29, 57, 6, -56, -95, -39, -22, -76, -22, -71, -68, 34, 79, 64, -97, 55, -86, -49, 72, -89, -95, -68, 49, 49, 81, -49, -41, 39, 39, -47, 8, -6, 88, 93, 27, 56, 33, -39, 19, -18, 85, 58, 36, 15, -39, -47, 33, -81, 53, -80, -26, -54, -46, -78, 74, 16, -14, -77, 61, 97, 39, -14, 95, 7, -24, -37, 71, -96, 72, 12, -61, 36, -3, -37, -67, 27, -31, -50, -5, 73, -7, -48, 39, -82, 41, 51, -36, 8, 54, 43, 60, 61, 35, 12, -86, 63, -87, -84, 52, -62, 59, -14, 38, 87, -84, -17, 62, 66, 22, -81, 80, -35, -83, 80, 44, 33, -33, 0, 60, -60, 0, 75, 0, -75, 80, -80, 20, -20}; //gil262.tsp
        double[] ypa561 = {543, 546, 536, 549, 560, 587, 611, 604, 601, 577, 573, 556, 556, 556, 591, 604, 622, 615, 591, 591, 584, 477, 429, 433, 474, 505, 518, 532, 529, 501, 467, 488, 460, 457, 484, 522, 522, 525, 518, 501, 494, 505, 491, 484, 460, 464, 467, 467, 419, 439, 433, 433, 409, 419, 412, 384, 374, 402, 426, 422, 409, 398, 398, 360, 378, 381, 364, 395, 398, 391, 395, 381, 360, 347, 354, 367, 343, 347, 319, 333, 302, 295, 247, 309, 288, 268, 261, 230, 216, 364, 364, 347, 333, 343, 323, 350, 299, 326, 326, 326, 299, 257, 292, 223, 182, 525, 494, 484, 498, 467, 470, 457, 443, 436, 436, 426, 422, 405, 402, 391, 391, 388, 378, 350, 371, 367, 364, 323, 340, 343, 330, 340, 350, 357, 323, 336, 402, 388, 464, 467, 453, 419, 436, 436, 412, 398, 381, 409, 340, 371, 378, 350, 539, 518, 546, 512, 525, 549, 549, 525, 512, 491, 464, 481, 402, 443, 450, 470, 419, 433, 439, 488, 488, 457, 429, 429, 398, 388, 384, 360, 350, 340, 316, 305, 295, 309, 302, 309, 268, 275, 305, 281, 250, 271, 247, 230, 216, 268, 261, 230, 237, 213, 202, 199, 292, 292, 268, 244, 261, 240, 223, 220, 220, 192, 343, 316, 343, 309, 309, 302, 285, 305, 275, 254, 271, 271, 250, 398, 371, 350, 367, 381, 374, 347, 326, 305, 350, 336, 319, 316, 244, 216, 213, 220, 247, 257, 278, 292, 299, 316, 340, 299, 226, 223, 230, 244, 216, 209, 185, 192, 158, 178, 182, 182, 154, 275, 250, 275, 288, 257, 254, 230, 250, 206, 220, 182, 154, 202, 206, 185, 257, 299, 281, 268, 247, 250, 268, 230, 206, 175, 161, 158, 134, 134, 151, 147, 123, 110, 116, 116, 89, 79, 86, 65, 44, 44, 44, 44, 10, 144, 144, 130, 116, 110, 116, 116, 137, 116, 92, 68, 92, 51, 48, 646, 649, 622, 604, 622, 653, 646, 683, 673, 735, 683, 721, 762, 745, 749, 787, 762, 790, 783, 694, 687, 714, 742, 732, 766, 769, 787, 773, 804, 807, 845, 845, 817, 852, 876, 890, 890, 903, 835, 852, 862, 896, 924, 896, 921, 948, 921, 951, 986, 962, 979, 962, 993, 996, 965, 1000, 797, 800, 769, 783, 821, 783, 824, 790, 780, 845, 886, 893, 824, 838, 896, 896, 927, 934, 653, 618, 591, 604, 625, 653, 653, 625, 646, 670, 649, 628, 622, 642, 659, 677, 659, 632, 656, 683, 677, 680, 707, 732, 707, 683, 690, 718, 714, 749, 762, 742, 728, 690, 718, 742, 752, 735, 694, 683, 701, 728, 756, 752, 732, 762, 735, 711, 718, 718, 749, 776, 793, 752, 721, 714, 745, 787, 787, 756, 718, 639, 656, 677, 677, 646, 615, 618, 663, 718, 687, 718, 656, 635, 625, 625, 601, 611, 653, 683, 666, 690, 532, 560, 584, 584, 598, 615, 598, 584, 560, 532, 539, 549, 570, 598, 618, 594, 536, 604, 584, 584, 611, 512, 498, 470, 488, 457, 426, 398, 398, 422, 484, 474, 532, 508, 529, 594, 580, 628, 580, 570, 505, 457, 443, 405, 426, 474, 494, 464, 415, 402, 384, 402, 374, 347, 323, 343, 347, 398, 422, 457, 460, 460, 536, 580, 584, 549, 577, 529, 529, 580, 604, 584, 529, 498, 484, 518, 577, 549, 477, 443, 443, 491}; //pa561.tsp
        double[] ygr666 = {0 ,-156.47 ,-147.43 ,-149.53 ,-134.27 ,-123.07 ,-113.28 ,-114.05 ,-104.39 ,-106.38 ,-97.09 ,-94.1 ,-79.23 ,-75.42 ,-73.34 ,-71.14 ,-63.36 ,-52.43 ,-122.2 ,-117.23 ,-121.3 ,-122.24 ,-118.15 ,-117.09 ,-111.53 ,-112.05 ,-105.01 ,-106.4 ,-106.29 ,-92.06 ,-93.13 ,-95.57 ,-94.39 ,-97.32 ,-96.48 ,-95.22 ,-87.55 ,-87.38 ,-90.25 ,-90.03 ,-90.07 ,-83.03 ,-80 ,-84.31 ,-84.23 ,-71.04 ,-74.01 ,-75.07 ,-77.01 ,-81.4 ,-80.12 ,-77.21 ,-106.05 ,-103.26 ,-100.19 ,-97.51 ,-100.59 ,-103.2 ,-99.09 ,-98.12 ,-96.4 ,-99.55 ,-96.43 ,-92.55 ,-89.37 ,-88.12 ,-90.31 ,-89.12 ,-87.13 ,-86.17 ,-84.05 ,-79.32 ,-82.22 ,-79.58 ,-75.49 ,-76.48 ,-72.2 ,-69.54 ,-66.07 ,-61.05 ,-59.37 ,-61.31 ,-68.56 ,-52.2 ,-55.1 ,-58.1 ,-66.56 ,-71.37 ,-74.48 ,-75.35 ,-74.05 ,-76.31 ,-91.01 ,-78.3 ,-78.38 ,-79.5 ,-73.15 ,-79.02 ,-77.03 ,-71.59 ,-71.33 ,-68.09 ,-63.1 ,-65.45 ,-70.24 ,-70.4 ,-73.03 ,-70.55 ,-57.51 ,-62.17 ,-57.33 ,-56.12 ,-58.27 ,-60.4 ,-64.11 ,-68.49 ,-65.13 ,-57.4 ,-51.11 ,-48.34 ,-49.15 ,-46.37 ,-43.14 ,-43.3 ,-43.56 ,-54.37 ,-56.05 ,-49.16 ,-47.55 ,-38.31 ,-34.54 ,-35.13 ,-38.3 ,-42.49 ,-44.16 ,-48.29 ,-60.01 ,-63.54 ,-23.31 ,-15.24 ,-16.54 ,-8 ,-7.35 ,-6.51 ,-4.57 ,-5.45 ,-0.43 ,3.03 ,5.3 ,6.37 ,10.11 ,10.46 ,13.11 ,20.04 ,29.54 ,32.18 ,32.33 ,31.15 ,32.53 ,37.14 ,32.32 ,30.13 ,25.21 ,38.53 ,38.5 ,43.09 ,-15.57 ,-17.26 ,-16.39 ,-15.35 ,-3.01 ,-8 ,-9.18 ,-13.43 ,-13.15 ,-10.47 ,-4.02 ,-1.35 ,-0.13 ,1.13 ,2.37 ,-1.31 ,2.07 ,8.3 ,13.1 ,15.03 ,3.24 ,7.27 ,6.44 ,8.47 ,11.31 ,18.35 ,9.27 ,15.17 ,15.18 ,18.16 ,22.25 ,25.12 ,29.22 ,30.04 ,32.25 ,36.49 ,45.2 ,39.4 ,39.11 ,39.17 ,13.14 ,15.47 ,27.28 ,28.13 ,28.17 ,28.36 ,31.03 ,35 ,34.52 ,32.35 ,-5.42 ,-12.3 ,14.31 ,17.06 ,15.1 ,25.55 ,28.1 ,28 ,26.07 ,30.56 ,27.55 ,25.4 ,18.22 ,43.4 ,47.31 ,49.17 ,57.3 ,55.27 ,-25.4 ,-9.08 ,-8.36 ,-5.59 ,-6.18 ,-4.25 ,-3.41 ,-4.46 ,-0.29 ,-0.22 ,2.11 ,-0.53 ,-3.41 ,-4.43 ,-2.58 ,-8.23 ,1.26 ,2.39 ,1.31 ,-0.34 ,1.26 ,5.24 ,7.15 ,7.23 ,9.27 ,1.16 ,4.24 ,4.51 ,5.43 ,-4.29 ,-1.41 ,-1.33 ,0.41 ,0.08 ,2.2 ,4.02 ,5.01 ,6.12 ,7.45 ,6.09 ,5.34 ,4.2 ,3.04 ,3.43 ,4.25 ,5.28 ,4.28 ,4.54 ,5.08 ,6.33 ,-4.1 ,-1.54 ,-0.08 ,-3.13 ,-2.35 ,-0.1 ,-1.5 ,-2.55 ,-2.15 ,-1.3 ,-1.35 ,-1.35 ,-3.13 ,-4.15 ,-3 ,-2.04 ,-1.09 ,-6.46 ,-8.28 ,-8.38 ,-6.15 ,-5.55 ,-7.19 ,-21.51 ,-51.44 ,-68.47 ,23.42 ,17.25 ,25.28 ,23.45 ,22.17 ,24.58 ,10.25 ,5.2 ,5.45 ,10.45 ,11.58 ,13 ,15.37 ,18.03 ,18.18 ,10.13 ,10.23 ,12.35 ,8.49 ,9.59 ,10.08 ,12.07 ,7.37 ,9.44 ,11.38 ,13.24 ,6.05 ,7.05 ,6.59 ,6.47 ,7.17 ,7.01 ,7.13 ,7.13 ,7.28 ,9.29 ,11.01 ,11.58 ,12.2 ,12.55 ,13.44 ,6.59 ,8.4 ,8.43 ,9.56 ,11.04 ,8.24 ,9.11 ,12.06 ,11.34 ,6.09 ,6.38 ,7.26 ,7.35 ,8.32 ,11.24 ,13.02 ,14.18 ,16.2 ,15.27 ,7.4 ,9.12 ,11 ,12.21 ,13.46 ,8.57 ,11.2 ,11.15 ,12.28 ,9 ,12.29 ,14.17 ,15.34 ,16.52 ,17.15 ,15.33 ,15.06 ,13.21 ,14.31 ,14.32 ,18.4 ,18 ,16.55 ,19.3 ,21 ,23.09 ,17 ,19 ,19.58 ,22.35 ,13.23 ,14.26 ,18.17 ,16.37 ,17.07 ,21.15 ,19.05 ,21.38 ,18.13 ,20.09 ,21.13 ,23.36 ,27.35 ,24.09 ,25.37 ,26.06 ,28.39 ,14.31 ,14.27 ,15.58 ,16.27 ,18.25 ,20.3 ,18.07 ,21.26 ,19.5 ,23.19 ,24.45 ,27.55 ,27.28 ,19.56 ,22.56 ,21.44 ,23.43 ,25.09 ,33.22 ,33.05 ,40.32 ,30.15 ,24.45 ,24.06 ,20.3 ,25.19 ,27.34 ,24 ,30.31 ,30.44 ,37.35 ,44 ,49.08 ,50.09 ,39.1 ,36.15 ,34.59 ,33.32 ,39.42 ,44.25 ,48.03 ,44.49 ,44.3 ,49.51 ,56.15 ,60.36 ,63.58 ,88.06 ,73.24 ,82.55 ,92.5 ,73.1 ,76.57 ,69.18 ,66.48 ,68.48 ,87.35 ,104.2 ,106.53 ,113.3 ,129.49 ,177.29 ,158.39 ,150.48 ,127.32 ,137.02 ,135.06 ,142.42 ,131.56 ,28.58 ,27.09 ,32.52 ,35.3 ,37.02 ,41.17 ,40.14 ,35.18 ,37.1 ,36.43 ,36.18 ,35.3 ,35.56 ,35 ,34.46 ,35.14 ,39.36 ,39.12 ,39.49 ,44.12 ,42.57 ,45.12 ,49.08 ,58.35 ,55.18 ,51.32 ,50.35 ,46.43 ,47.59 ,47.47 ,44.25 ,44.28 ,43.08 ,46.18 ,49.36 ,51.26 ,47.04 ,48.16 ,51.38 ,52.32 ,57.05 ,59.36 ,62.12 ,65.3 ,69.12 ,73.04 ,74.18 ,73.05 ,71.29 ,67 ,68.52 ,68.22 ,67.03 ,78.02 ,77.13 ,73.02 ,75.49 ,80.21 ,83 ,85.07 ,88.22 ,72.37 ,79.06 ,85.5 ,72.5 ,78.29 ,83.18 ,75.1 ,77.35 ,80.17 ,78.41 ,78.07 ,79.51 ,85.19 ,89.39 ,90.25 ,91.5 ,96.05 ,96.1 ,98.59 ,102.08 ,102.36 ,105.51 ,107.36 ,108.13 ,106.4 ,104.55 ,100.31 ,100.2 ,101.42 ,103.51 ,98.4 ,100.21 ,104.45 ,106.48 ,107.36 ,110.22 ,112.45 ,115.13 ,123.35 ,114.35 ,110.2 ,114.55 ,117.09 ,119.24 ,124.51 ,128.12 ,132.45 ,125.36 ,123.54 ,122.34 ,121 ,114.09 ,120.17 ,121.3 ,91.09 ,103.41 ,108.52 ,104.04 ,106.34 ,102.4 ,113.16 ,119.17 ,114.17 ,118.47 ,121.28 ,113.39 ,120.19 ,112.3 ,117.12 ,116.25 ,121.35 ,123.27 ,126.41 ,125.45 ,126.58 ,129.03 ,141.21 ,140.07 ,140.53 ,139.46 ,136.55 ,136.39 ,135.45 ,135.3 ,132.27 ,129.55 ,130.33 ,127.4 ,144.47 ,140.42 ,152.12 ,147.1 ,130.5 ,115.5 ,138.35 ,144.58 ,147.19 ,151.13 ,153.02 ,146.48 ,133.53 ,170.3 ,172.38 ,174.47 ,174.46 ,-175.12 ,-170.42 ,178.25 ,166.27 ,159.57 ,166.55 ,165.23 ,-157.52 ,-157.2 ,-139 ,-149.34 ,-130.06 ,-109.22 ,0}; //gr666.tsp
        
        System.out.println("");
        System.out.println("eil51");
        startexperiment(25, xeil51, yeil51);
        System.out.println("");
        System.out.println("rat99");
        startexperiment(49, xrat99, yrat99);
        System.out.println("");
        /*System.out.println("gr137");
        startexperiment(68, xgr137, ygr137);
        System.out.println("");
        System.out.println("gr229");
        startexperiment(114, xgr229, ygr229);
        System.out.println("");
        System.out.println("rd400");
        startexperiment(199, xrd400, yrd400);
        System.out.println("");
        System.out.println("pa561");
        startexperiment(280, xpa561, ypa561);*//**/
        /*System.out.println("");
        System.out.println("gr666");
        startexperiment(332, xgr666, ygr666);*/
        
        /*
        //var 1
        for (int i = 0; i < n; i++) {
            //q[i] = ThreadLocalRandom.current().nextInt(1, 10 + 1);
            q[i] = 1;
            q[i + n] = -q[i];
        }
        StopRule=n;
        S=n;
        System.out.println(S + " " + StopRule);
        for (int i = 1; i <= 10; i++) {
            //heuristic(n, StopRule, S, path, q, c);
        }
        for (int ki = 1; ki<=1; ki++) {
        long timer = System.nanoTime();
        //System.out.println("R^1");
        double PMin=100500;
        double CoeffMin=0;
        int RMin=1;
        for (int i = 1; i<=1000; i++) {
            double m;
            m = (double) i / 100;
            for (int j=1; j<2;j++) {
                double Dtemp;
                Dtemp = gravitysearch(n, S, q, c, m, j);
                if (PMin>Dtemp) {
                    PMin=Dtemp;
                    CoeffMin=m;
                    RMin=j;
                }
            }
        }

        double elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", CoeffMin);
        System.out.print("  ");
        System.out.print(RMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        
        timer = System.nanoTime();
        PMin=1000000000;
        CoeffMin=0;
        RMin=1;
        for (int i = 1; i<2; i++) {
            double m;
            m = (double) i / 100;
            for (int j=1; j<2;j++) {
                double Dtemp;
                Dtemp = altgravitysearch(n, S, q, c, i, j);
                if (PMin>Dtemp) {
                    PMin=Dtemp;
                    CoeffMin=i;
                    RMin=j;
                }
                Dtemp = altgravitysearch(n, S, q, c, -i, j);
                if (PMin>Dtemp) {
                    PMin=Dtemp;
                    CoeffMin=-i;
                    RMin=j;
                }
            }
        }

        //gravitys4opto(n, S, q, c, CoeffMin, RMin, n);
        
        elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", CoeffMin);
        System.out.print("  ");
        System.out.print(RMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        
        
        greedsearch(n, S, q, c);
        
        long timer = System.nanoTime();
        //System.out.println("R^1");
        double PMin=1000000000;
        double CoeffMin=0;
        int RMin=1;
        int SMin=1;
        for (int i = 1; i<=1000; i++) {
            double m;
            m = (double) i / 100;
            
                double Dtemp;
                Dtemp = alt2gravitysearch(n, S, q, c, m, 2, 1);
                if (PMin>Dtemp) {
                    PMin=Dtemp;
                    CoeffMin=m;
                    RMin=1;
                    SMin=2;
                }
            
        }

        double elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", CoeffMin);
        System.out.print("  ");
        System.out.print(SMin);
        System.out.print("  ");
        System.out.print(RMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        
        }
        
        //var 2
        for (int i = 0; i < n; i++) {
            //q[i] = ThreadLocalRandom.current().nextInt(1, 10 + 1);
            q[i] = i;
            q[i + n] = -q[i];
        }
        StopRule=n;
        S=n;
        System.out.println(S + " " + StopRule);
        for (int i = 0; i < 10; i++) {
            //heuristic(n, StopRule, S, path, q, c);
        }
        for (int ki = 1; ki<=1; ki++) {
        long timer = System.nanoTime();
        //System.out.println("R^1");
        double PMin=1000000000;
        double CoeffMin=0;
        int RMin=1;
        for (int i = 1; i<=2000; i++) {
            double m;
            m = (double) i / 100;
            for (int j=1; j<21;j++) {
                double Dtemp;
                Dtemp = gravitysearch(n, S, q, c, m, j);
                if (PMin>Dtemp) {
                    PMin=Dtemp;
                    CoeffMin=m;
                    RMin=j;
                }
            }
        }

        double elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", CoeffMin);
        System.out.print("  ");
        System.out.print(RMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        
        timer = System.nanoTime();
        PMin=1000000000;
        CoeffMin=0;
        RMin=1;
        for (int i = 1; i<61; i++) {
            double m;
            m = (double) i / 100;
            for (int j=1; j<61;j++) {
                double Dtemp;
                Dtemp = altgravitysearch(n, S, q, c, i, j);
                if (PMin>Dtemp) {
                    PMin=Dtemp;
                    CoeffMin=i;
                    RMin=j;
                }
                Dtemp = altgravitysearch(n, S, q, c, -i, j);
                if (PMin>Dtemp) {
                    PMin=Dtemp;
                    CoeffMin=-i;
                    RMin=j;
                }
            }
        }

        //gravitys4opto(n, S, q, c, CoeffMin, RMin, n);
        
        elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", CoeffMin);
        System.out.print("  ");
        System.out.print(RMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        
        
        greedsearch(n, S, q, c);
        long timer = System.nanoTime();
        //System.out.println("R^1");
        double PMin=1000000000;
        double CoeffMin=0;
        int RMin=1;
        int SMin=1;
        for (int i = 1; i<=1000; i++) {
            double m;
            m = (double) i / 100;
            for (int j=1; j<21;j++) { for (int s=0; s<3;s++) {
                double Dtemp;
                Dtemp = alt2gravitysearch(n, S, q, c, m, s, j);
                if (PMin>Dtemp) {
                    PMin=Dtemp;
                    CoeffMin=m;
                    RMin=j;
                    SMin=s;
                }
                Dtemp = alt2gravitysearch(n, S, q, c, m, -s, j);
                if (PMin>Dtemp) {
                    PMin=Dtemp;
                    CoeffMin=m;
                    RMin=j;
                    SMin=-s;
                }
            }}
        }

        double elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", CoeffMin);
        System.out.print("  ");
        System.out.print(SMin);
        System.out.print("  ");
        System.out.print(RMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        }
        
        //var 3
        for (int i = 0; i < n; i++) {
            //q[i] = ThreadLocalRandom.current().nextInt(1, 10 + 1);
            q[i] = i;
            q[i + n] = -q[i];
        }
        StopRule=n;
        S=3*n;
        System.out.println(S + " " + StopRule);
        for (int i = 1; i <= 1; i++) {
            //heuristic(n, StopRule, S, path, q, c);
        }
        for (int ki = 1; ki<=1; ki++) {
        long timer = System.nanoTime();
        //System.out.println("R^1");
        double PMin=100500;
        double CoeffMin=0;
        int RMin=1;
        for (int i = 1; i<=1000; i++) {
            double m;
            m = (double) i / 100;
            for (int j=1; j<20;j++) {
                double Dtemp;
                Dtemp = gravitysearch(n, S, q, c, m, j);
                if (PMin>Dtemp) {
                    PMin=Dtemp;
                    CoeffMin=m;
                    RMin=j;
                }
            }
        }

        double elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", CoeffMin);
        System.out.print("  ");
        System.out.print(RMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        
        timer = System.nanoTime();
        PMin=1000000000;
        CoeffMin=0;
        RMin=1;
        for (int i = 1; i<61; i++) {
            double m;
            m = (double) i / 100;
            for (int j=1; j<61;j++) {
                double Dtemp;
                Dtemp = altgravitysearch(n, S, q, c, i, j);
                if (PMin>Dtemp) {
                    PMin=Dtemp;
                    CoeffMin=i;
                    RMin=j;
                }
                Dtemp = altgravitysearch(n, S, q, c, -i, j);
                if (PMin>Dtemp) {
                    PMin=Dtemp;
                    CoeffMin=-i;
                    RMin=j;
                }
            }
        }

        //gravitys4opto(n, S, q, c, CoeffMin, RMin, n);
        
        elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", CoeffMin);
        System.out.print("  ");
        System.out.print(RMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        
        
        greedsearch(n, S, q, c);*/
        /*long timer = System.nanoTime();
        //System.out.println("R^1");
        double PMin=1000000000;
        double CoeffMin=0;
        int RMin=1;
        int SMin=1;
        for (int i = 1; i<=1000; i++) {
            double m;
            m = (double) i / 100;
            for (int j=1; j<21;j++) { for (int s=0; s<3;s++) {
                double Dtemp;
                Dtemp = alt2gravitysearch(n, S, q, c, m, s, j);
                if (PMin>Dtemp) {
                    PMin=Dtemp;
                    CoeffMin=m;
                    RMin=j;
                    SMin=s;
                }
                Dtemp = alt2gravitysearch(n, S, q, c, m, -s, j);
                if (PMin>Dtemp) {
                    PMin=Dtemp;
                    CoeffMin=m;
                    RMin=j;
                    SMin=-s;
                }
            }}
        }

        double elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", CoeffMin);
        System.out.print("  ");
        System.out.print(SMin);
        System.out.print("  ");
        System.out.print(RMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        }*/
        /*System.out.println("Greed");
        greedsearch(n, S, q, c);*/
        
        /*
        S = 10;
        System.out.println(S + " " + 100);
        for (int i = 1; i <= 10; i++) {
            heuristic(n, 100, S, path, q, c);
        }
        System.out.println(S + " " + 200);
        for (int i = 1; i <= 10; i++) {
            heuristic(n, 200, S, path, q, c);
        }
        System.out.println(S + " " + 500);
        for (int i = 1; i <= 10; i++) {
            heuristic(n, 500, S, path, q, c);
        }
        System.out.println(S + " " + 1000);
        for (int i = 1; i <= 10; i++) {
            heuristic(n, 1000, S, path, q, c);
        }
        */
        //S = 100;
        /*System.out.println(S + " " + 100);
        for (int i = 1; i <= 10; i++) {
            heuristic(n, 100, S, path, q, c);
        }
        System.out.println(S + " " + 200);
        for (int i = 1; i <= 10; i++) {
            heuristic(n, 200, S, path, q, c);
        }
        System.out.println(S + " " + 500);
        for (int i = 1; i <= 10; i++) {
            heuristic(n, 500, S, path, q, c);
        }
        System.out.println(S + " " + 1000);
        for (int i = 1; i <= 10; i++) {
            heuristic(n, 1000, S, path, q, c);
        }
        */
        //S = n;
        /*System.out.println(S + " " + 65);
        for (int i = 1; i <= 10; i++) {
            heuristic(n, 65, S, path, q, c);
        }
        System.out.println(S + " " + 130);
        for (int i = 1; i <= 10; i++) {
            heuristic(n, 130, S, path, q, c);
        }
        System.out.println(S + " " + 260);
        for (int i = 1; i <= 10; i++) {
            heuristic(n, 260, S, path, q, c);
        }*/
        
        
        /*
        double dist = distance(2 * n, path, c);
        double tdist;
        System.out.println(dist);
        
        Chain tmpc = new Chain(2*n);
        
        int i, j;
        int count = 0;
        
        do
        {
            i = ThreadLocalRandom.current().nextInt(1, n + 1);
            do {
                j = ThreadLocalRandom.current().nextInt(1, n + 1);
            } while (i==j);
            //System.out.println(n+ " "+ i + " " + j);
            tmpc.Chain(path, 2 * n, i, j, i + n, j + n);
            tmpc.Split();
            tdist = dist;
            int[] h = new int[1];
            int kmax = tmpc.getM();
            for (int ki = 0; ki < kmax; ki++) {
                for (int kin = 0; kin < kmax + 1; kin++) {
                    for (int kj = 0; kj < kmax + 2; kj++) {
                        for (int kjn = 0; kjn < kmax + 3; kjn++) {
                            tmpc.Chain(path, 2 * n, i, j, i + n, j + n);
                            tmpc.Split();
                            h[0] = i;
                            tmpc.InsertLink(h, 1, ki);
                            h[0] = i + n;
                            tmpc.InsertLink(h, 1, kin);
                            h[0] = j;
                            tmpc.InsertLink(h, 1, kj);
                            h[0] = j + n;
                            tmpc.InsertLink(h, 1, kjn);
                            if ((tdist > distance(2 * n, tmpc.Path(), c))&&(correct(2 * n, S, tmpc.Path(), q))) {
                                tdist = distance(2 * n, tmpc.Path(), c);
                                tmppath = tmpc.Path();
                            }
                        }
                    }
                }
            }
        if (tdist<dist) {
            dist = tdist;
            path = tmppath;
            count = 0;
        }
        else {
            count++;
        }
        } while (count<100);
        
        System.out.println(dist);
        System.out.println(correct(2 * n, S, path, q));
        /*for (int k = 0; k < 2*n; k++) {
            System.out.println((k+1) + " " + path[k] + " " + q[path[k] - 1]);
        }*/
        

        //testchain.PrintChains();
        
        /*
        for (int i = 0; i < 2* n; i++) {
            System.out.print(path[i] + " ");
        }
        System.out.println("");
        System.out.println(S);
        for (int i = 0; i < 2* n; i++) {
            System.out.print(q[path[i] - 1] + " ");
        }
        System.out.println("");
        System.out.println(correct(2*n, S, path, q));
        
        
        Chain testchain = new Chain(2*n);
        int i = 1;
        int j = 2;
        testchain.Chain(path, 2 * n, i, j, i + n, j + n);
        testchain.PrintChains();
        testchain.Split();
        testchain.PrintChains();
        
        int[] testpath = new int[2*n - 4];
        testpath = testchain.Path();
        
        for (int k = 0; k < 2*n - 4; k++) {
            System.out.print(testpath[k] + " ");
        }*/
        
        /*int[] link = {5, 4, 3, 2, 1};
        int[] link2 = {4, 3, 2, 1};
        testchain.AddLink(link2, 4);
        testchain.AddLink(link2, 4);
        testchain.InsertLink(link, 5, 0);
        testchain.InsertLink(link, 5, 2);
        testchain.PrintChainsFullTest();
        testchain.PrintChains();*/
    }
    
    public static double polaralpha(double x, double y) {
        double z = Math.sqrt(x * x + y * y);
        if ((x>0)&(y>0)) {
            return Math.acos(x / z);
        }
        else if ((x<0)&(y>0)) {
            return Math.acos(x / z);
        }
        else if ((x<0)&(y<0)) {
            return Math.acos(-x / z) + Math.PI;
        }
        else if ((x>0)&(y<0)) {
            return Math.acos(-x / z) + Math.PI;
        }
        else if ((x==0)&(y>0)) {
            return Math.PI / 2;
        }
        else if ((x==0)&(y<0)) {
            return 3 * Math.PI / 2;
        }
        else if ((x>0)&(y==0)) {
            return 0;
        }
        else if ((x<0)&(y==0)) {
            return Math.PI;
        }
        else {
            return 0;
        }
    }
    
    public static void startexperiment(int n, double[] x, double[] y) {
        // TODO code application logic here
        int[] path = new int[2*n];
        double[] q = new double[2*n];
        
        double[][] c = new double[2*n + 1][2*n + 1];
        double[][] alpha = new double[2*n + 1][2*n + 1];
        double S = 0;
        for (int i = 0; i < n; i++) {
            path[2 * i] = i + 1;
            path[2 * i + 1] = i + 1 + n;
            //System.out.print(path[i] + " ");
        }
        
        
        System.out.println("");
        for (int i = 0; i < n; i++) {
            //q[i] = ThreadLocalRandom.current().nextInt(1, 10 + 1);
            q[i] = i;
            if (S < q[i]) {
                S = q[i];
            }
            q[i + n] = -q[i];
        }
        
        //System.out.println("");
        for (int i = 0; i <= 2*n; i++) {
            for (int j = 0; j <= 2*n; j++) {
                alpha[i][j] = polaralpha((x[i] - x[j]), (y[i] - y[j]));
                c[i][j] = Math.pow(Math.pow((x[i] - x[j]), 2) + Math.pow((y[i] - y[j]), 2),0.5);
            }
            //System.out.println("");
        }
        
        
        
        //var 1 (first half is 1, second is 2)
        System.out.println("Var 1");
        for (int i = 0; i < n; i++) {
            //q[i] = ThreadLocalRandom.current().nextInt(1, 10 + 1);
            if (i<(n/2)) {
                q[i] = 1;
            }
            else {
                q[i] = 2;
            }
            q[i + n] = -q[i];
        }
        System.out.println("S = 4");
        startspecificexperiment(n, q, c, alpha,  4);
        System.out.println("S = 6");
        startspecificexperiment(n, q, c, alpha,  6);
        System.out.println("S = 10");
        startspecificexperiment(n, q, c, alpha,  10);
        
        //var 2 (1, 2, 3, 4, 5 in circles)
        System.out.println("Var 2");
        int k = 0;
        for (int i = 0; i < n; i++) {
            //q[i] = ThreadLocalRandom.current().nextInt(1, 10 + 1);
            k++;
            if (k==6) { k = 1; }
            q[i] = k;
            q[i + n] = -q[i];
        }
        System.out.println("S = 5");
        startspecificexperiment(n, q, c, alpha,  5);
        System.out.println("S = 10");
        startspecificexperiment(n, q, c, alpha,  10);
        System.out.println("S = 15");
        startspecificexperiment(n, q, c, alpha,  15);
        System.out.println("S = 20");
        startspecificexperiment(n, q, c, alpha,  20);
        
        //var 3 (qi = i, S = 3*n)
        System.out.println("Var 3");
        for (int i = 0; i < n; i++) {
            q[i] = i;
            q[i + n] = -q[i];
        }
        System.out.println("S = 3*n");
        startspecificexperiment(n, q, c, alpha, 3*n);
        
    }
    
    public static void startspecificexperiment(int n, double[] q, double[][] c, double[][] alpha, double S)
    {
        int StopRule = n;
        int[] path = new int[2*n];
        for (int i = 0; i < n; i++) {
            path[2 * i] = i + 1;
            path[2 * i + 1] = i + 1 + n;
            //System.out.print(path[i] + " ");
        }
        
        //System.out.println("4-opt-o " + S + " " + StopRule);
        for (int i = 1; i <= 10; i++) {
            //heuristic(n, StopRule, S, path, q, c);
        }
        
        //my LISE
        /*long timer = System.nanoTime();
        System.out.println("LISE");
        double PMin=1000000000;
        double CoeffMin=0;
        int RMin=1;
        int SMin=1;
        int FB = 0;
                
        for (int i = 1; i<=100; i++) {
            double m;
            m = (double) i / 10;
            for (int j=1; j<21;j++) { for (int s=-2; s<3;s++) {
                double Dtemp;
                Dtemp = alt2gravitysearch(n, S, q, c, m, s, j);
                if (PMin>Dtemp) {
                    PMin=Dtemp;
                    CoeffMin=m;
                    RMin=j;
                    SMin=s;
                    FB = 0;
                }
            }}
        }
        
        for (int i = 1; i<=100; i++) {
            double m;
            m = (double) i / 10;
            for (int j=1; j<21;j++) { for (int s=-2; s<3;s++) {
                double Dtemp;
                Dtemp = alt2gravitysearchreverse(n, S, q, c, m, s, j);
                if (PMin>Dtemp) {
                    PMin=Dtemp;
                    CoeffMin=m;
                    RMin=j;
                    SMin=s;
                    FB = 1;
                }
            }}
        }
        
        System.out.println("");
        double elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", CoeffMin);
        System.out.print("  ");
        System.out.print(SMin);
        System.out.print("  ");
        System.out.print(RMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.print("  ");
        System.out.print(FB);
        System.out.println("");*/
        
        //BEM LISE
        /*long timer = System.nanoTime();
        System.out.println("LISE");
        double PMin=1000000000;
        int RMin=1;
        int SMin=1;
        for (int j=1; j<101;j++) { for (int s=-1; s<2;s++) {
            double Dtemp;
            Dtemp = altgravitysearch(n, S, q, c, s, j);
            if (PMin>Dtemp) {
                PMin=Dtemp;
                RMin=j;
                SMin=s;
            }
        }}
        
        System.out.println("");
        double elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.print(SMin);
        System.out.print("  ");
        System.out.print(RMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");*/
        
        
        //4-opt var 2
        /*timer = System.nanoTime();
        PMin=1000000000;
        for (int i = 1; i<=100; i++) {
            double m;
            m = (double) i / 10;
            for (int j=1; j<21;j++) { for (int s=-2; s<3;s++) {
                double Dtemp;
                Dtemp = alt2gravitysearch(n, S, q, c, m, s, j);
                if (PMin>Dtemp) {
                    PMin=Dtemp;
                    CoeffMin=m;
                    RMin=j;
                    SMin=s;
                    FB = 0;
                }
            }}
        }
        
        for (int i = 1; i<=100; i++) {
            double m;
            m = (double) i / 10;
            for (int j=1; j<21;j++) { for (int s=-2; s<3;s++) {
                double Dtemp;
                Dtemp = alt2gravitysearchreverse(n, S, q, c, m, s, j);
                if (PMin>Dtemp) {
                    PMin=Dtemp;
                    CoeffMin=m;
                    RMin=j;
                    SMin=s;
                    FB = 1;
                }
            }}
        }
        double elapsedtmp = (System.nanoTime() - timer);
        System.out.println("4-opt-o with start path from LISE");
        for (int i = 1; i <= 10; i++) {
            timer = System.nanoTime();
            if (FB==0) {
                gravitys4opto(n, S, q, c, CoeffMin, SMin, RMin, n);
            }
            else {
                gravitys4optoreverse(n, S, q, c, CoeffMin, SMin, RMin, n);
            }
            elapsed = (System.nanoTime() - timer + elapsedtmp);
            System.out.print("  ");
            System.out.printf("%.5f", elapsed/1000000000);
            System.out.println("");
        }*/
        
        //Combo LISE - discarded
        /*
        long timer = System.nanoTime();
        System.out.println("LISE");
        double PMin=1000000000;
        double CoeffMin=0;
        int RMin=1;
        int SMin=1;
        int PiMin=1;
                
        for (int i = 1; i<=1000; i++) {
            double m;
            m = (double) i / 100;
            for (int j=1; j<21;j++) {
                for (int s=-2; s<3;s++) {
                    for (int k = 0; k<=20; k++) {
                        double Dtemp;
                        //double p = (double) k/10;
                        Dtemp = altgravitysearchcombo(n, S, q, c, m, s, j, k);
                        if (PMin>Dtemp) {
                            PMin=Dtemp;
                            CoeffMin=m;
                            RMin=j;
                            SMin=s;
                            PiMin = k;
                        }
                    }
                }
            }
        }
        
        System.out.println("");
        double elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", CoeffMin);
        System.out.print("  ");
        System.out.print(SMin);
        System.out.print("  ");
        System.out.print(RMin);
        System.out.print("  ");
        System.out.print(PiMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        */
        
        
        //greedsearch(n, S, q, c);
        
        //Firefly search
        
        long timer = System.nanoTime();
        double PMin = particle(n, S, q, c, 50, 1);
        double elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        
        timer = System.nanoTime();
        PMin = particle(n, S, q, c, 50, 2);
        elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        
        timer = System.nanoTime();
        PMin = particle(n, S, q, c, 50, 3);
        elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        
        timer = System.nanoTime();
        PMin = particle(n, S, q, c, 50, 4);
        elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        
        timer = System.nanoTime();
        PMin = particle(n, S, q, c, 50, 5);
        elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        
        timer = System.nanoTime();
        PMin = particle(n, S, q, c, 50, 6);
        elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        
        timer = System.nanoTime();
        PMin = particle(n, S, q, c, 50, 7);
        elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        
        timer = System.nanoTime();
        PMin = particle(n, S, q, c, 50, 8);
        elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        
        timer = System.nanoTime();
        PMin = particle(n, S, q, c, 50, 9);
        elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        
        timer = System.nanoTime();
        PMin = particle(n, S, q, c, 50, 10);
        elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", PMin);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.println("");
        
        //System.out.println(ameabesearch(n, S, q, c, alpha, 1, 1, 2));
    }
    
    public static double distance(int n, int[] path, double[][] c) {
        double dist = 0;
        for (int i = 1; i < n; i++) {
            dist = dist + c[path[i - 1]][path[i]];
        }
        dist = c[0][path[0]] + dist + c[path[n - 1]][0];
        return dist;
    }
    
    public static boolean correct(int n, double S, int[] path, double[] q) {
        double load = 0;
        for (int i = 0; i < n; i++) {
            load = load + q[path[i] - 1];
            if ((load < 0)||(load > S)) {
                return false;
            }
        }
        for (int i = 1; i <= (int) n / 2; i++) {
            // TO DO: i+n after i
            int k;
            for (k = 0; k < n; k++) {
                if (path[k] == i) {
                    break;
                }
            }
            int j;
            for (j = 0; j < n; j++) {
                if (path[j] == i + (int) n / 2) {
                    break;
                }
            }
            if (j < k) {
                return false;
            }
        }
        return true;
    }
    
    public static void heuristic(int n, int RuleCount, double S, int[] path, double[] q, double[][] c) {
        long timer = System.nanoTime();
        int[] tmppath = new int[2*n];
        double dist = distance(2 * n, path, c);
        double tdist;
        //System.out.println(dist);
        
        Chain tmpc = new Chain(2*n);
        
        int i, j;
        int count = 0;
        int iters = 0;
        
        do
        {
            iters++;
            i = ThreadLocalRandom.current().nextInt(1, n + 1);
            do {
                j = ThreadLocalRandom.current().nextInt(1, n + 1);
            } while (i==j);
            //System.out.println(n+ " "+ i + " " + j);
            tmpc.Chain(path, 2 * n, i, j, i + n, j + n);
            tmpc.Split();
            tdist = dist;
            int[] h = new int[1];
            int kmax = tmpc.getM();
            for (int ki = 0; ki <= kmax; ki++) {
                for (int kin = ki; kin <= kmax + 1; kin++) { // for (int kin = 0; kin <= kmax + 1; kin++) {
                    for (int kj = 0; kj <= kmax + 2; kj++) { 
                        for (int kjn = kj; kjn <= kmax + 3; kjn++) { // for (int kjn = 0; kjn <= kmax + 3; kjn++) {
                            tmpc.Chain(path, 2 * n, i, j, i + n, j + n);
                            tmpc.Split();
                            h[0] = i;
                            tmpc.InsertLink(h, 1, ki);
                            h[0] = i + n;
                            tmpc.InsertLink(h, 1, kin);
                            h[0] = j;
                            tmpc.InsertLink(h, 1, kj);
                            h[0] = j + n;
                            tmpc.InsertLink(h, 1, kjn);
                            if ((tdist > distance(2 * n, tmpc.Path(), c))&&(correct(2 * n, S, tmpc.Path(), q))) {
                                tdist = distance(2 * n, tmpc.Path(), c);
                                tmppath = tmpc.Path();
                            }
                        }
                    }
                }
            }
        if (tdist<dist) {
            dist = tdist;
            path = tmppath;
            count = 0;
        }
        else {
            count++;
        }
        } while (count<RuleCount);
        
        double elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", dist);
        System.out.print("   " + iters + "   ");
        System.out.printf("%.5f", elapsed/1000000000);
        //System.out.println(" " + correct(2 * n, S, path, q));
        System.out.println("");
        /*for (int k = 0; k < 2*n; k++) {
            System.out.println((k+1) + " " + path[k] + " " + q[path[k] - 1]);
        }*/
    }
    
    public static double gravitysearch(int n, double S, double[] q, double[][] c, double VehCharge, int RType) { //RType = 1, 2, 3
        long timer = System.nanoTime();
        double AverageCharge=0;
        int[] path = new int[2*n + 1];
        double dist = 0;
        double[] charge = new double[2*n];
        double VehicleCharge = 0;
        double VehicleS = 0;
        double qmax=0;
        for (int i = 0; i < n; i++) {
            if (qmax<q[i]) {
                qmax=q[i];
            }
        }
        for (int i = 0; i < n; i++) {
            charge[i] = q[i]/qmax;
            charge[i+n] = 0;
            AverageCharge+=charge[i];
        }
        AverageCharge/=n;
        VehicleCharge=AverageCharge*VehCharge; // var 1
        //VehicleCharge=S*VehCharge; // var 2
        double cmax = 0;
        //System.out.println("");
        for (int i = 0; i <= 2*n; i++) {
            for (int j = 0; j <= 2*n; j++) {
                if (c[i][j]>cmax) {
                    cmax=c[i][j];
                }
            }
        }
        path[0] = 0;
        
        for (int i = 0; i<2*n; i++) {
            double MaxForce = 0; // =0 for LISA; =2*cmax for greed
            path[i + 1]=1;
            for (int j = 1; j<=2*n; j++) {
                double Force;
                if ((path[i]!=j)&&((VehicleS + q[j - 1])>=0)&&((VehicleS + q[j - 1])<=S)) {
                    double r2 = 1;
                    r2 = Math.pow((c[path[i]][j] / cmax), RType);
                    if (j > n + 1) {
                        Force = (charge[j - 1] * charge[j - 1]) / r2; // LISA
                    }
                    else {
                        Force = (VehicleCharge*charge[j - 1]) / r2; // LISA
                    }
                    if (MaxForce<Force) { //LISA
                        MaxForce=Force;
                        path[i + 1] = j;
                    }
                }
            }
            //System.out.println(i + " " + path[i + 1]);
            if (path[i + 1] > n) {
                charge[path[i + 1] - 1] = 0;
            }
            else {
                charge[path[i + 1] + n - 1] = charge[path[i + 1] - 1];
                charge[path[i + 1] - 1] = 0;
            }
            dist+=c[path[i]][path[i + 1]];
            VehicleS+=q[path[i + 1] - 1];
            //VehicleCharge=(S - VehicleS)*VehCharge; // var 2
        }
        dist+=c[path[2*n]][0];
        double elapsed = (System.nanoTime() - timer);
        /*int[] cpath = new int[2*n];
        for (int i = 0; i < 2*n; i++){
            cpath[i]=path[i + 1];
            //System.out.println(cpath[i]);
        }
        if (correct(2 * n, S, cpath, q)) {
            System.out.printf("%.5f", dist);
            System.out.print("   ");
            System.out.printf("%.5f", elapsed/1000000000);
            System.out.print("   ");
            System.out.printf("%.5f", VehCharge);
        }
        
        if (false) {
            //int[] cpath = new int[2*n];
            for (int i = 0; i < 2*n; i++){
                cpath[i]=path[i + 1];
                //System.out.println(cpath[i]);
            }
            if (correct(2 * n, S, cpath, q)) {
                System.out.print("Всё корректно");
            }
        }
        System.out.println("");*/
        return dist;
    }
    
    
    public static void greedsearch(int n, double S, double[] q, double[][] c) {
        long timer = System.nanoTime();
        
        int[] path = new int[2*n + 1];
        double dist = 0;
        boolean[] visited = new boolean[2*n];
        boolean[] ready = new boolean[2*n];
        double VehicleS = 0;

        for (int i = 0; i < 2*n; i++) {
            visited[i] = false;
        }
        for (int i = 0; i < n; i++) {
            ready[i] = true;
            ready[i + n] = false;
        }
        
        double cmax = 0;
        //System.out.println("");
        for (int i = 0; i <= 2*n; i++) {
            for (int j = 0; j <= 2*n; j++) {
                if (c[i][j]>cmax) {
                    cmax=c[i][j];
                }
            }
        }
        path[0] = 0;
        
        for (int i = 0; i<2*n; i++) {
            double MaxLength = cmax*2; // =0 for LISA; =2*cmax for greed
            path[i + 1]=1;
            for (int j = 1; j<=2*n; j++) {
                double Length = c[path[i]][j];
                if (((path[i]!=j)&&((VehicleS + q[j - 1])>=0)&&((VehicleS + q[j - 1])<=S))&&!(visited[j-1])&&(ready[j-1])) {
                    //System.out.println(i + " " + j);
                    if (MaxLength>Length) {
                        MaxLength=Length;
                        path[i + 1] = j;
                    }
                }
            }
            //System.out.println(i + " " + path[i + 1]);
            if (path[i + 1] > n) {
                visited[path[i + 1] - 1] = true;
            }
            else {
                ready[path[i + 1] + n - 1] = true;
                visited[path[i + 1] - 1] = true;
            }
            dist+=c[path[i]][path[i + 1]];
            VehicleS+=q[path[i + 1] - 1];
        }
        dist+=c[path[2*n]][0];
        double elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f",dist);
        System.out.print("  ");
        System.out.printf("%.5f", elapsed/1000000000);
        System.out.print("  ");
        if (false) {
            int[] cpath = new int[2*n];
            for (int i = 0; i < 2*n; i++){
                cpath[i]=path[i + 1];
                //System.out.println(cpath[i]);
            }
            if (correct(2 * n, S, cpath, q)) {
                System.out.print("Всё корректно");
            }
        }
        System.out.println("");
    }
    
    
    public static void gravitys4opto(int n, double S, double[] q, double[][] c, double R, int s, int t, int RuleCount) {
        long timer = System.nanoTime();
        double AverageCharge=0;
        int[] path = new int[2*n + 1];
        double dist = 0;
        double[] charge = new double[2*n];
        double VehicleCharge = 0;
        double VehicleS = 0;
        double qmax=0;
        for (int i = 0; i < n; i++) {
            if (qmax<q[i]) {
                qmax=q[i];
            }
        }
        for (int i = 0; i < n; i++) {
            charge[i] = q[i]/qmax;
            AverageCharge+=charge[i];
        }
        AverageCharge/=n;
        VehicleCharge=AverageCharge*R; // var 1
        //VehicleCharge=S*VehCharge; // var 2
        double cmax = 0;
        //System.out.println("");
        for (int i = 0; i <= 2*n; i++) {
            for (int j = 0; j <= 2*n; j++) {
                if (c[i][j]>cmax) {
                    cmax=c[i][j];
                }
            }
        }
        path[0] = 0;
        
        for (int i = 0; i<2*n; i++) {
            double MaxForce = 0; // =0 for LISA; =2*cmax for greed
            path[i + 1]=1;
            for (int j = 1; j<=2*n; j++) {
                double Force;
                if ((path[i]!=j)&&((VehicleS + q[j - 1])>=0)&&((VehicleS + q[j - 1])<=S)) {
                    
                    double r1, r2 = 1;
                    r1 = charge[j - 1];
                    if (r1<0) {r1 *= -1;}
                    if (charge[j - 1] == 0)
                    {
                        r1 = 0;
                    }
                    else if (s==0)
                        {
                            r1 = 1;
                        }
                    else if (s==1)
                        {
                            r1 = r1;
                        }
                    else if (s==2)
                        {
                            r1 = r1*r1;
                        }
                    else if (s==-1)
                        {
                            r1 = 1/r1;
                        }
                    else if (s==-2)
                        {
                            r1 = 1/(r1*r1);
                        }
                    r2 = Math.pow((c[path[i]][j]/cmax), t);
                    
                    if (j > n + 1) {
                        Force = (r1 * charge[j - 1]) / r2; // LISA
                    }
                    else {
                        Force = (VehicleCharge * r1) / r2; // LISA
                    }
                    
                    if (MaxForce<Force) { //LISA
                        MaxForce=Force;
                        path[i + 1] = j;
                    }

                }
            }
            //System.out.println(i + " " + path[i + 1]);
            if (path[i + 1] > n) {
                charge[path[i + 1] - 1] = 0;
            }
            else {
                charge[path[i + 1] + n - 1] = charge[path[i + 1] - 1];
                charge[path[i + 1] - 1] = 0;
            }
            dist+=c[path[i]][path[i + 1]];
            VehicleS+=q[path[i + 1] - 1];
            //VehicleCharge=(S - VehicleS)*VehCharge; // var 2
        }
        dist+=c[path[2*n]][0];
        
        /*int[] cpath = new int[2*n];
        for (int i = 0; i < 2*n; i++){
            cpath[i]=path[i + 1];
            //System.out.println(cpath[i]);
        }
        if (correct(2 * n, S, cpath, q)) {
            System.out.printf("%.5f", dist);
            System.out.print("   ");
            System.out.printf("%.5f", elapsed/1000000000);
            System.out.print("   ");
            System.out.printf("%.5f", VehCharge);
        }
        
        if (false) {
            //int[] cpath = new int[2*n];
            for (int i = 0; i < 2*n; i++){
                cpath[i]=path[i + 1];
                //System.out.println(cpath[i]);
            }
            if (correct(2 * n, S, cpath, q)) {
                System.out.print("Всё корректно");
            }
        }
        System.out.println("");*/
        double initdist = dist;
                
        int[] cpath = new int[2*n];
        for (int i=0; i<2*n;i++)
        {
            cpath[i] = path[i+1];
        }
        
        int[] tmppath = new int[2*n];
        
        double tdist;
        //System.out.println(dist);
        
        Chain tmpc = new Chain(2*n);
        
        int i, j;
        int count = 0;
        int iters = 0;
        
        do
        {
            iters++;
            i = ThreadLocalRandom.current().nextInt(1, n + 1);
            do {
                j = ThreadLocalRandom.current().nextInt(1, n + 1);
            } while (i==j);
            //System.out.println(n+ " "+ i + " " + j);
            tmpc.Chain(cpath, 2 * n, i, j, i + n, j + n);
            tmpc.Split();
            tdist = dist;
            int[] h = new int[1];
            int kmax = tmpc.getM();
            for (int ki = 0; ki <= kmax; ki++) {
                for (int kin = ki; kin <= kmax + 1; kin++) { // for (int kin = 0; kin <= kmax + 1; kin++) {
                    for (int kj = 0; kj <= kmax + 2; kj++) { 
                        for (int kjn = kj; kjn <= kmax + 3; kjn++) { // for (int kjn = 0; kjn <= kmax + 3; kjn++) {
                            tmpc.Chain(cpath, 2 * n, i, j, i + n, j + n);
                            tmpc.Split();
                            h[0] = i;
                            tmpc.InsertLink(h, 1, ki);
                            h[0] = i + n;
                            tmpc.InsertLink(h, 1, kin);
                            h[0] = j;
                            tmpc.InsertLink(h, 1, kj);
                            h[0] = j + n;
                            tmpc.InsertLink(h, 1, kjn);
                            if ((tdist > distance(2 * n, tmpc.Path(), c))&&(correct(2 * n, S, tmpc.Path(), q))) {
                                tdist = distance(2 * n, tmpc.Path(), c);
                                tmppath = tmpc.Path();
                            }
                        }
                    }
                }
            }
        if (tdist<dist) {
            dist = tdist;
            cpath = tmppath;
            count = 0;
        }
        else {
            count++;
        }
        } while (count<RuleCount);
        
        double elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", initdist);
        System.out.print("   ");
        System.out.printf("%.5f", dist);
        System.out.print("   " + iters + "   ");
        //System.out.printf("%.5f", elapsed/1000000000);
        //System.out.println(" " + correct(2 * n, S, path, q));
        //System.out.println("");
        /*for (int k = 0; k < 2*n; k++) {
            System.out.println((k+1) + " " + path[k] + " " + q[path[k] - 1]);
        }*/
        
    }
        
    public static double altgravitysearch(int n, double S, double[] q, double[][] c, int s, int t) { //RType = 1, 2, 3
        long timer = System.nanoTime();
        int[] path = new int[2*n + 1];
        double dist = 0;
        double[] charge = new double[2*n];
        
        double VehicleS = 0;
        double qmax=0;
        for (int i = 0; i < n; i++) {
            if (qmax<q[i]) {
                qmax=q[i];
            }
        }
        for (int i = 0; i < n; i++) {
            charge[i] = q[i];
            charge[i+n] = 0;
        }

        
        path[0] = 0;
        
        for (int i = 0; i<2*n; i++) {
            double MaxForce = 0; // =0 for LISA; =2*cmax for greed
            path[i + 1]=1;
            for (int j = 1; j<=2*n; j++) {
                double Force;
                if ((path[i]!=j)&&((VehicleS + q[j - 1])>=0)&&((VehicleS + q[j - 1])<=S)) {
                    double r1, r2 = 1;
                    if (charge[j - 1] == 0) {
                        r1 = 0;
                    }
                    else if (s==1) {
                        r1 = charge[j - 1];
                    }
                    else if (s==0) {
                        r1 = 1;
                    }
                    else {
                        r1 = 1 / charge[j - 1];
                    }
                    
                    r2 = Math.pow((c[path[i]][j]), t);
                    Force = r1 / r2; // LISA
                    if (MaxForce<Force) { //LISA
                        MaxForce=Force;
                        path[i + 1] = j;
                    }
                }
            }
            //System.out.println(i + " " + path[i + 1]);
            if (path[i + 1] > n) {
                charge[path[i + 1] - 1] = 0;
            }
            else {
                charge[path[i + 1] + n - 1] = charge[path[i + 1] - 1];
                charge[path[i + 1] - 1] = 0;
            }
            dist+=c[path[i]][path[i + 1]];
            VehicleS+=q[path[i + 1] - 1];
            //VehicleCharge=(S - VehicleS)*VehCharge; // var 2
        }
        dist+=c[path[2*n]][0];
        double elapsed = (System.nanoTime() - timer);
        /*int[] cpath = new int[2*n];
        for (int i = 0; i < 2*n; i++){
            cpath[i]=path[i + 1];
            //System.out.println(cpath[i]);
        }
        if (correct(2 * n, S, cpath, q)) {
            System.out.printf("%.5f", dist);
            System.out.print("   ");
            System.out.printf("%.5f", elapsed/1000000000);
            System.out.print("   ");
            System.out.printf("%.5f", VehCharge);
        }
        
        if (false) {
            //int[] cpath = new int[2*n];
            for (int i = 0; i < 2*n; i++){
                cpath[i]=path[i + 1];
                //System.out.println(cpath[i]);
            }
            if (correct(2 * n, S, cpath, q)) {
                System.out.print("Всё корректно");
            }
        }
        System.out.println("");*/
        return dist;
    }
    
    
    public static double alt2gravitysearch(int n, double S, double[] q, double[][] c, double R, int s, int t) { //RType = 1, 2, 3
        long timer = System.nanoTime();
        int[] path = new int[2*n + 1];
        double dist = 0;
        double[] charge = new double[2*n];
        double VehicleS = 0;
        double qmax=0;
        for (int i = 0; i < n; i++) {
            if (qmax<q[i]) {
                qmax=q[i];
            }
        }
        
        double VehicleCharge, AverageCharge = 0;
        for (int i = 0; i < n; i++) {
            charge[i] = q[i]/qmax;
            charge[i+n] = 0;
            AverageCharge+=charge[i];
        }
        AverageCharge/=n;
        VehicleCharge=AverageCharge*R;

        double cmax = 0;
        //System.out.println("");
        for (int i = 0; i <= 2*n; i++) {
            for (int j = 0; j <= 2*n; j++) {
                if (c[i][j]>cmax) {
                    cmax=c[i][j];
                }
            }
        }        
        
        double[][] cr2 = new double[2*n + 1][2*n + 1];
        for (int i = 0; i <= 2*n; i++) {
            for (int j = i; j <= 2*n; j++) {
                cr2[i][j]=0;
                if (c[i][j]!=0) {
                    double temp = c[i][j] / cmax;
                    cr2[i][j]=1;
                    for (int k1 = 1; k1 <= t; k1++) {cr2[i][j]*=temp;}
                    cr2[j][i]=cr2[i][j];
                }
            }
        }
        
        path[0] = 0;
        
        for (int i = 0; i<2*n; i++) {
            double MaxForce = 0; // =0 for LISA; =2*cmax for greed
            path[i + 1]=1;
            for (int j = 1; j<=2*n; j++) {
                double Force;
                if ((path[i]!=j)&&((VehicleS + q[j - 1])>=0)&&((VehicleS + q[j - 1])<=S)) {
                    
                    double r1 = 1, r2 = 1;
                    r1 = charge[j - 1];
                    if (r1<0) {r1 *= -1;}
                    if (charge[j - 1] == 0)
                    {
                        r1 = 0;
                    }
                    else if ((charge[j - 1] == 1)||(charge[j - 1] == -1))
                    {
                        r1 = 1;
                    }
                    else if (s==0)
                        {
                            r1 = 1;
                        }
                    /*else if (s==1)
                        {
                            r1 = charge[j - 1];
                        }
                    else if (s==2)
                        {
                            r1 = charge[j - 1]*charge[j - 1];
                        }
                    else if (s==-1)
                        {
                            r1 = 1 / charge[j - 1];
                        }
                    else if (s==-2)
                        {
                            r1 = 1 / (charge[j - 1]*charge[j - 1]);
                        }*/
                    else if (s>0)
                        {
                            double r1t = 1;
                            for (int k1 = 1; k1 <= s; k1++) {r1t *= charge[j - 1];}
                            r1 = r1t;
                        }
                    else if (s<0)
                        {
                            double r1t = 1;
                            for (int k1 = 1; k1 <= -s; k1++) {r1t *= charge[j - 1];}
                            r1 = 1 / r1t;
                        }
                    //r1 = charge[j - 1];
                    if (r1<0) {r1 *= -1;}
                    r2 = cr2[path[i]][j];
                    
                    if (j > n + 1) {
                        Force = (r1 * charge[j - 1]) / r2; // LISA
                    }
                    else {
                        Force = (VehicleCharge * r1) / r2; // LISA 1
                        //Force = (R * r1 * charge[j - 1]) / r2; // LISA 2
                    }
                    
                    if (MaxForce<Force) { //LISA
                        MaxForce=Force;
                        path[i + 1] = j;
                    }

                }
            }
            //System.out.println(i + " " + path[i + 1]);
            if (path[i + 1] > n) {
                charge[path[i + 1] - 1] = 0;
            }
            else {
                charge[path[i + 1] + n - 1] = charge[path[i + 1] - 1];
                charge[path[i + 1] - 1] = 0;
            }
            dist+=c[path[i]][path[i + 1]];
            VehicleS+=q[path[i + 1] - 1];
            //VehicleCharge=(S - VehicleS)*VehCharge; // var 2
        }
        dist+=c[path[2*n]][0];
        double elapsed = (System.nanoTime() - timer);
        /*int[] cpath = new int[2*n];
        for (int i = 0; i < 2*n; i++){
            cpath[i]=path[i + 1];
            //System.out.println(cpath[i]);
        }
        if (correct(2 * n, S, cpath, q)) {
            System.out.printf("%.5f", dist);
            System.out.print("   ");
            System.out.printf("%.5f", elapsed/1000000000);
            System.out.print("   ");
            System.out.printf("%.5f", VehCharge);
        }
        
        if (false) {
            //int[] cpath = new int[2*n];
            for (int i = 0; i < 2*n; i++){
                cpath[i]=path[i + 1];
                //System.out.println(cpath[i]);
            }
            if (correct(2 * n, S, cpath, q)) {
                System.out.print("Всё корректно");
            }
        }
        System.out.println("");*/
        return dist;
    }
    
    public static double alt2gravitysearchreverse(int n, double S, double[] q, double[][] c, double R, int s, int t) { //RType = 1, 2, 3
        long timer = System.nanoTime();
        int[] path = new int[2*n + 1];
        double dist = 0;
        double[] charge = new double[2*n];
        double VehicleS = 0;
        double qmax=0;
        for (int i = 0; i < n; i++) {
            if (qmax<q[i]) {
                qmax=q[i];
            }
        }
        
        double VehicleCharge, AverageCharge = 0;
        for (int i = 0; i < n; i++) {
            charge[i+n] = q[i]/qmax;
            charge[i] = 0;
            AverageCharge+=charge[i+n];
        }
        AverageCharge/=n;
        VehicleCharge=AverageCharge*R;

        double cmax = 0;
        //System.out.println("");
        for (int i = 0; i <= 2*n; i++) {
            for (int j = 0; j <= 2*n; j++) {
                if (c[i][j]>cmax) {
                    cmax=c[i][j];
                }
            }
        }        
        
        double[][] cr2 = new double[2*n + 1][2*n + 1];
        for (int i = 0; i <= 2*n; i++) {
            for (int j = i; j <= 2*n; j++) {
                cr2[i][j]=0;
                if (c[i][j]!=0) {
                    double temp = c[i][j] / cmax;
                    cr2[i][j]=1;
                    for (int k1 = 1; k1 <= t; k1++) {cr2[i][j]*=temp;}
                    cr2[j][i]=cr2[i][j];
                }
            }
        }
        
        path[0] = 0;
        
        for (int i = 0; i<2*n; i++) {
            double MaxForce = 0; // =0 for LISA; =2*cmax for greed
            path[i + 1]=1;
            for (int j = 1; j<=2*n; j++) {
                double Force;
                if (i==0) {
                    if (j > n + 1) {
                        double r2 = cr2[path[i]][j];
                        Force = 1 / r2;
                        if (MaxForce<Force) { //LISA
                        MaxForce=Force;
                        path[i + 1] = j;
                    }
                    }
                }
                else if ((path[i]!=j)&&((VehicleS + q[j - 1])<=0)&&((VehicleS + q[j - 1])>=-S)) {
                    
                    double r1 = 1, r2 = 1;
                    r1 = charge[j - 1];
                    if (r1<0) {r1 *= -1;}
                    if (charge[j - 1] == 0)
                    {
                        r1 = 0;
                    }
                    else if ((charge[j - 1] == 1)||(charge[j - 1] == -1))
                    {
                        r1 = 1;
                    }
                    else if (s==0)
                        {
                            r1 = 1;
                        }
                    /*else if (s==1)
                        {
                            r1 = charge[j - 1];
                        }
                    else if (s==2)
                        {
                            r1 = charge[j - 1]*charge[j - 1];
                        }
                    else if (s==-1)
                        {
                            r1 = 1 / charge[j - 1];
                        }
                    else if (s==-2)
                        {
                            r1 = 1 / (charge[j - 1]*charge[j - 1]);
                        }*/
                    else if (s>0)
                        {
                            double r1t = 1;
                            for (int k1 = 1; k1 <= s; k1++) {r1t *= charge[j - 1];}
                            r1 = r1t;
                        }
                    else if (s<0)
                        {
                            double r1t = 1;
                            for (int k1 = 1; k1 <= -s; k1++) {r1t /= charge[j - 1];}
                            r1 = r1t;
                        }
                    //r1 = charge[j - 1];
                    if (r1<0) {r1 *= -1;}
                    r2 = cr2[path[i]][j];
                    
                    if (j > n + 1) {
                        Force = (r1 * charge[j - 1]) / r2; // LISA
                    }
                    else {
                        Force = (VehicleCharge * r1) / r2; // LISA 1
                        //Force = (R * r1 * charge[j - 1]) / r2; // LISA 2
                    }
                    
                    if (MaxForce<Force) { //LISA
                        MaxForce=Force;
                        path[i + 1] = j;
                    }

                }
            }
            //System.out.println(i + " " + path[i + 1]);
            if (path[i + 1] <= n) {
                charge[path[i + 1] - 1] = 0;
            }
            else {
                //System.out.println(path[i + 1]);
                charge[path[i + 1] - n - 1] = charge[path[i + 1] - 1];
                charge[path[i + 1] - 1] = 0;
            }
            dist+=c[path[i]][path[i + 1]];
            VehicleS+=q[path[i + 1] - 1];
            //VehicleCharge=(S - VehicleS)*VehCharge; // var 2
        }
        dist+=c[path[2*n]][0];
        
        /*double elapsed = (System.nanoTime() - timer);
        int[] cpath = new int[2*n];
        for (int i = 0; i < 2*n; i++){
            cpath[i]=path[2*n - i];
            //System.out.println(cpath[i]);
        }
        if (correct(2 * n, S, cpath, q)) {
            System.out.printf("%.5f", dist);
            System.out.print("   ");
            //System.out.printf("%.5f", elapsed/1000000000);
        }
        
        if (true) {
            //int[] cpath = new int[2*n];
            for (int i = 0; i < 2*n; i++){
                cpath[i] = path[2*n - i];
                //System.out.println(cpath[i]);
            }
            if (correct(2 * n, S, cpath, q)) {
                System.out.print("Всё корректно ");
                System.out.print(distance(2*n, cpath, c));
            }
        }
        System.out.println("");*/
        return dist;
    }
    
    public static void gravitys4optoreverse(int n, double S, double[] q, double[][] c, double R, int s, int t, int RuleCount) {
        long timer = System.nanoTime();
        int[] path = new int[2*n + 1];
        double dist = 0;
        double[] charge = new double[2*n];
        double VehicleS = 0;
        double qmax=0;
        for (int i = 0; i < n; i++) {
            if (qmax<q[i]) {
                qmax=q[i];
            }
        }
        
        double VehicleCharge, AverageCharge = 0;
        for (int i = 0; i < n; i++) {
            charge[i+n] = q[i]/qmax;
            charge[i] = 0;
            AverageCharge+=charge[i+n];
        }
        AverageCharge/=n;
        VehicleCharge=AverageCharge*R;

        double cmax = 0;
        //System.out.println("");
        for (int i = 0; i <= 2*n; i++) {
            for (int j = 0; j <= 2*n; j++) {
                if (c[i][j]>cmax) {
                    cmax=c[i][j];
                }
            }
        }        
        
        double[][] cr2 = new double[2*n + 1][2*n + 1];
        for (int i = 0; i <= 2*n; i++) {
            for (int j = i; j <= 2*n; j++) {
                cr2[i][j]=0;
                if (c[i][j]!=0) {
                    double temp = c[i][j] / cmax;
                    cr2[i][j]=1;
                    for (int k1 = 1; k1 <= t; k1++) {cr2[i][j]*=temp;}
                    cr2[j][i]=cr2[i][j];
                }
            }
        }
        
        path[0] = 0;
        
        for (int i = 0; i<2*n; i++) {
            double MaxForce = 0; // =0 for LISA; =2*cmax for greed
            path[i + 1]=1;
            for (int j = 1; j<=2*n; j++) {
                double Force;
                if (i==0) {
                    if (j > n + 1) {
                        double r2 = cr2[path[i]][j];
                        Force = 1 / r2;
                        if (MaxForce<Force) { //LISA
                        MaxForce=Force;
                        path[i + 1] = j;
                    }
                    }
                }
                else if ((path[i]!=j)&&((VehicleS + q[j - 1])<=0)&&((VehicleS + q[j - 1])>=-S)) {
                    
                    double r1, r2 = 1;
                    r1 = charge[j - 1];
                    if (r1<0) {r1 *= -1;}
                    if (charge[j - 1] == 0)
                    {
                        r1 = 0;
                    }
                    else if (s==0)
                        {
                            r1 = 1;
                        }
                    else if (s==1)
                        {
                            r1 = r1;
                        }
                    else if (s==2)
                        {
                            r1 = r1*r1;
                        }
                    else if (s==-1)
                        {
                            r1 = 1/r1;
                        }
                    else if (s==-2)
                        {
                            r1 = 1/(r1*r1);
                        }
                    r2 = cr2[path[i]][j];
                    
                    if (j > n + 1) {
                        Force = (r1 * charge[j - 1]) / r2; // LISA
                    }
                    else {
                        Force = (VehicleCharge * r1) / r2; // LISA
                    }
                    
                    if (MaxForce<Force) { //LISA
                        MaxForce=Force;
                        path[i + 1] = j;
                    }

                }
            }
            //System.out.println(i + " " + path[i + 1]);
            if (path[i + 1] <= n) {
                charge[path[i + 1] - 1] = 0;
            }
            else {
                //System.out.println(path[i + 1]);
                charge[path[i + 1] - n - 1] = charge[path[i + 1] - 1];
                charge[path[i + 1] - 1] = 0;
            }
            dist+=c[path[i]][path[i + 1]];
            VehicleS+=q[path[i + 1] - 1];
            //VehicleCharge=(S - VehicleS)*VehCharge; // var 2
        }
        dist+=c[path[2*n]][0];
        
        
        int[] cpath = new int[2*n];
        for (int i = 0; i < 2*n; i++){
            cpath[i]=path[2*n - i];
            //System.out.println(cpath[i]);
        }
        /*if (correct(2 * n, S, cpath, q)) {
            System.out.printf("%.5f", dist);
            System.out.print("   ");
            System.out.printf("%.5f", elapsed/1000000000);
            System.out.print("   ");
            System.out.printf("%.5f", VehCharge);
        }
        
        if (false) {
            //int[] cpath = new int[2*n];
            for (int i = 0; i < 2*n; i++){
                cpath[i]=path[i + 1];
                //System.out.println(cpath[i]);
            }
            if (correct(2 * n, S, cpath, q)) {
                System.out.print("Всё корректно");
            }
        }
        System.out.println("");*/
        double initdist = dist;
                
        /*int[] cpath = new int[2*n];
        for (int i=0; i<2*n;i++)
        {
            cpath[i] = path[i+1];
        }*/
        
        int[] tmppath = new int[2*n];
        
        double tdist;
        //System.out.println(dist);
        
        Chain tmpc = new Chain(2*n);
        
        int i, j;
        int count = 0;
        int iters = 0;
        
        do
        {
            iters++;
            i = ThreadLocalRandom.current().nextInt(1, n + 1);
            do {
                j = ThreadLocalRandom.current().nextInt(1, n + 1);
            } while (i==j);
            //System.out.println(n+ " "+ i + " " + j);
            tmpc.Chain(cpath, 2 * n, i, j, i + n, j + n);
            tmpc.Split();
            tdist = dist;
            int[] h = new int[1];
            int kmax = tmpc.getM();
            for (int ki = 0; ki <= kmax; ki++) {
                for (int kin = ki; kin <= kmax + 1; kin++) { // for (int kin = 0; kin <= kmax + 1; kin++) {
                    for (int kj = 0; kj <= kmax + 2; kj++) { 
                        for (int kjn = kj; kjn <= kmax + 3; kjn++) { // for (int kjn = 0; kjn <= kmax + 3; kjn++) {
                            tmpc.Chain(cpath, 2 * n, i, j, i + n, j + n);
                            tmpc.Split();
                            h[0] = i;
                            tmpc.InsertLink(h, 1, ki);
                            h[0] = i + n;
                            tmpc.InsertLink(h, 1, kin);
                            h[0] = j;
                            tmpc.InsertLink(h, 1, kj);
                            h[0] = j + n;
                            tmpc.InsertLink(h, 1, kjn);
                            if ((tdist > distance(2 * n, tmpc.Path(), c))&&(correct(2 * n, S, tmpc.Path(), q))) {
                                tdist = distance(2 * n, tmpc.Path(), c);
                                tmppath = tmpc.Path();
                            }
                        }
                    }
                }
            }
        if (tdist<dist) {
            dist = tdist;
            cpath = tmppath;
            count = 0;
        }
        else {
            count++;
        }
        } while (count<RuleCount);
        
        double elapsed = (System.nanoTime() - timer);
        System.out.printf("%.5f", initdist);
        System.out.print("   ");
        System.out.printf("%.5f", dist);
        System.out.print("   " + iters + "   ");
        //System.out.printf("%.5f", elapsed/1000000000);
        //System.out.println(" " + correct(2 * n, S, path, q));
        //System.out.println("");
        /*for (int k = 0; k < 2*n; k++) {
            System.out.println((k+1) + " " + path[k] + " " + q[path[k] - 1]);
        }*/
        
    }
    
    
    
    public static double altgravitysearchcombo(int n, double S, double[] q, double[][] c, double R, int s, int t, double p) { //RType = 1, 2, 3
        long timer = System.nanoTime();
        int[] path = new int[2*n + 1];
        double dist = 0;
        double[] charge = new double[2*n];
        double VehicleS = 0;
        double qmax=0;
        for (int i = 0; i < n; i++) {
            if (qmax<q[i]) {
                qmax=q[i];
            }
        }
        
        double VehicleCharge, AverageCharge = 0;
        for (int i = 0; i < n; i++) {
            charge[i] = q[i]/qmax;
            charge[i+n] = 0;
            AverageCharge+=charge[i];
        }
        AverageCharge/=n;
        VehicleCharge=AverageCharge*R;

        double cmax = 0;
        //System.out.println("");
        for (int i = 0; i <= 2*n; i++) {
            for (int j = 0; j <= 2*n; j++) {
                if (c[i][j]>cmax) {
                    cmax=c[i][j];
                }
            }
        }        
        
        double[][] cr2 = new double[2*n + 1][2*n + 1];//, cr3 = new double[2*n + 1][2*n + 1];
        for (int i = 0; i <= 2*n; i++) {
            for (int j = i; j <= 2*n; j++) {
                if (c[i][j]!=0) {
                    double temp = c[i][j] / cmax;
                    cr2[i][j]=1;
                    for (int k1 = 1; k1 <= t; k1++) {cr2[i][j]*=temp;}
                    cr2[j][i]=cr2[i][j];
                    /*cr3[i][j]=1;
                    for (int k1 = 1; k1 <= p; k1++) {cr3[i][j]*=c[i][j];}
                    cr3[j][i]=cr3[i][j];*/
                }
            }
        }
        /*double r3 = 1, rtemp = 0;
        for (int k1 = 1; k1 <= t; k1++) {r3*=VehicleCharge;}
        if (s>0)
            {
                double r3t = 1;
                for (int k1 = 1; k1 <= s; k1++) {r3t *= VehicleCharge;}
                r3 = r3t;
            }
        else if (s<0)
            {
                double r3t = 1;
                for (int k1 = 1; k1 <= -s; k1++) {r3t *= VehicleCharge;}
                r3 = 1 / r3t;
            }
        path[0] = 0;*/
        
        for (int i = 0; i<2*n; i++) {
            double MaxForce = 0; // =0 for LISA; =2*cmax for greed
            path[i + 1]=1;
            for (int j = 1; j<=2*n; j++) {
                double Force;
                //double rtemp = 1;
                if ((path[i]!=j)&&((VehicleS + q[j - 1])>=0)&&((VehicleS + q[j - 1])<=S)) {
                    
                    double r1 = 1, r2 = 1, r3 = 1;
                    r1 = charge[j - 1];
                    if (r1<0) {r1 *= -1;}
                    if (charge[j - 1] == 0)
                    {
                        r1 = 0;
                        r3 = 0;
                        //rtemp = 0;
                    }
                    else if ((charge[j - 1] == 1)||(charge[j - 1] == -1))
                    {
                        r1 = 1;
                    }
                    else if (s==0)
                        {
                            r1 = 1;
                            r3 = 1;
                        }
                    /*else if (s==1)
                        {
                            r1 = charge[j - 1];
                        }
                    else if (s==2)
                        {
                            r1 = charge[j - 1]*charge[j - 1];
                        }
                    else if (s==-1)
                        {
                            r1 = 1 / charge[j - 1];
                        }
                    else if (s==-2)
                        {
                            r1 = 1 / (charge[j - 1]*charge[j - 1]);
                        }*/
                    else if (s>0)
                        {
                            double r1t = 1;
                            for (int k1 = 1; k1 <= s; k1++) {r1t *= charge[j - 1]; r3 *= VehicleCharge;}
                            r1 = r1t;
                        }
                    else if (s<0)
                        {
                            double r1t = 1;
                            for (int k1 = 1; k1 <= -s; k1++) {r1t *= charge[j - 1]; r3 *= VehicleCharge;}
                            r1 = 1 / r1t;
                        }
                    //r1 = charge[j - 1];
                    if (r1<0) {r1 *= -1;}
                    r2 = cr2[path[i]][j];
                    //r3 = cr3[path[i]][j];
                    
                    if (j > n + 1) {
                        Force = (r1 * charge[j - 1]) / r2 + p * (VehicleCharge * r3) * (cr2[j][0]);
                        //Force = ((1 * r1 * charge[j - 1]) / r2) + (1 - p) * rtemp * (c[j][0] / r3); // var 1
                        //Force = (r1 * charge[j - 1]) / (r2 * p + cr2[j][0] * (1 - p)); //var 2
                        //Force = ((p * r1 * charge[j - 1]) / r2) + (((1 - p) * charge[j - 1] * r1) / cr2[j][0]); // var 3
                    }
                    else {
                        Force = (VehicleCharge * r1) / r2 + p * (VehicleCharge * r3) * (cr2[j][0]); // LISA 1
                        //Force = (R * r1 * charge[j - 1]) / r2; // LISA 2
                    }
                    
                    if (MaxForce<Force) { //LISA
                        MaxForce=Force;
                        path[i + 1] = j;
                    }

                }
            }
            //System.out.println(i + " " + path[i + 1]);
            if (path[i + 1] > n) {
                charge[path[i + 1] - 1] = 0;
            }
            else {
                charge[path[i + 1] + n - 1] = charge[path[i + 1] - 1];
                charge[path[i + 1] - 1] = 0;
            }
            dist+=c[path[i]][path[i + 1]];
            VehicleS+=q[path[i + 1] - 1];
            //VehicleCharge=(S - VehicleS)*VehCharge; // var 2
        }
        dist+=c[path[2*n]][0];
        double elapsed = (System.nanoTime() - timer);
        int[] cpath = new int[2*n];
        /*for (int i = 0; i < 2*n; i++){
            cpath[i]=path[i + 1];
            //System.out.println(cpath[i]);
        }
        if (correct(2 * n, S, cpath, q)) {
            System.out.printf("%.5f", dist);
            System.out.print("   ");
            System.out.printf("%.5f", elapsed/1000000000);
            System.out.print("   ");
            System.out.printf("%.5f", VehCharge);
        }
        */
        if (true) {
            //int[] cpath = new int[2*n];
            for (int i = 0; i < 2*n; i++){
                cpath[i]=path[i + 1];
                //System.out.println(cpath[i]);
            }
            if (correct(2 * n, S, cpath, q)) {
            }
            else {
                System.out.print("Некорректно ");
                System.out.print(R);
                System.out.print(" ");
                System.out.print(s);
                System.out.print(" ");
                System.out.print(t);
                System.out.print(" ");
                System.out.print(p);
                /*System.out.print(" ");
                System.out.print(r3);*/
                System.out.print(" ");
                System.out.print(dist);
                for (int i = 0; i < 2*n; i++){
                    System.out.print(" ");
                    System.out.print(cpath[i]);
                }
                System.out.println("");
            }
        }
        return dist;
    }
    
    public static double particle(int n, double S, double[] q, double[][] c, int SwarmSize, double gamma) { //Particle Swarm Optimization
        double[][] particles = new double[SwarmSize][5];
        double[][] particlestmp = new double[SwarmSize][5];
        //particles[0]: length
        //particles[1]: R
        //particles[2]: s
        //particles[3]: t
        //particles[4]: 1 - forward, -1 - backward
        
        double initR = 0.01;
        int inits = -2;
        int initt = 1;
        int initF = 1;
        
        //generate particle swarm
        for (int i = 0; i < SwarmSize; i++) {
            particles[i][1] = initR;
            particles[i][2] = inits;
            particles[i][3] = initt;
            particles[i][4] = initF;
            
            if (particles[i][4] == -1) {
                particles[i][0] = alt2gravitysearch(n, S, q, c, particles[i][1], (int) particles[i][2], (int) particles[i][3]);
            }
            else {
                particles[i][0] = alt2gravitysearchreverse(n, S, q, c, particles[i][1], (int) particles[i][2], (int) particles[i][3]);
            }
            
            /*System.out.print(particles[i][1]);
            System.out.print(' ');
            System.out.print(particles[i][2]);
            System.out.print(' ');
            System.out.print(particles[i][3]);
            System.out.print(' ');
            System.out.print(particles[i][0]);
            System.out.println(' ');*/
            
            initR *= 3;
            inits += 1;
            initt += 3;
            initF *= -1;
            
            if (initR >= 25) {initR = 0.01;}
            if (inits == 3) {inits = -2;}
            if (initt > 25) {initt = 1;}
            
        }
        
        //start movement
        boolean state = true;
        double[][] attraction = new double[SwarmSize][SwarmSize];
        double[][] r = new double[SwarmSize][SwarmSize];
        double[] bestparticle = new double[5];
        int generations = 1;
        
        bestparticle[0] = particles[0][0];
        bestparticle[1] = particles[0][1];
        bestparticle[2] = particles[0][2];
        bestparticle[3] = particles[0][3];
        bestparticle[4] = particles[0][4];
        
        while (generations <= 20) {
            //calculate luminocities
            for (int i = 0; i < SwarmSize; i++) {
                particlestmp[i][0] = particles[i][0];
                particlestmp[i][1] = particles[i][1];
                particlestmp[i][2] = particles[i][2];
                particlestmp[i][3] = particles[i][3];
                particlestmp[i][4] = particles[i][4];
                
                if (bestparticle[0] > particles[i][0]) {
                    bestparticle[0] = particles[i][0];
                    bestparticle[1] = particles[i][1];
                    bestparticle[2] = particles[i][2];
                    bestparticle[3] = particles[i][3];
                    bestparticle[4] = particles[i][4];
                } 
                
                for (int j = i; j < SwarmSize; j++) {
                    if (i == j) {
                        attraction[i][j] = 0;
                    }
                    else {
                        double tmp = (particles[i][1] - particles[j][1]) * (particles[i][1] - particles[j][1]);
                        tmp += (particles[i][2] - particles[j][2]) * (particles[i][2] - particles[j][2]);
                        tmp += (particles[i][3] - particles[j][3]) * (particles[i][3] - particles[j][3]);
                        tmp += (particles[i][4] - particles[j][4]) * (particles[i][4] - particles[j][4]);
                        r[i][j] = tmp; // here be the formula for distance
                        r[j][i] = r[i][j];
                        if (particles[i][0] > particles[j][0]) {
                            attraction[i][j] = (particles[i][0] - particles[j][0]) * Math.pow(Math.exp(1), -gamma * r[i][j]); //formula requires to add distance as well
                            attraction[j][i] = 0;
                        }
                        else if (particles[i][0] < particles[j][0]) {
                            attraction[j][i] = (particles[j][0] - particles[i][0]) * Math.pow(Math.exp(1), -gamma * r[i][j]);;
                            attraction[i][j] = 0;
                        }
                        else {
                            attraction[i][j] = 0;
                            attraction[j][i] = 0;
                        }
                    }
                }
            }
            
            //calculate directions and movement
            for (int i = 0; i < SwarmSize; i++) {
                boolean isdirection = false;
                double currattr = 0;
                int direction = 0;
                
                for (int j = 0; j < SwarmSize; j++) {
                    if (attraction[i][j] > 0) {
                        isdirection = true;
                        if (attraction[i][j] > currattr) {
                            currattr = attraction[i][j];
                            direction = j;
                        }
                    }
                }
                if (isdirection) {
                    //Math.pow(Math.exp(1), -gamma * r[i][j])
                    particles[i][1] += 1 * (particlestmp[i][1] - particlestmp[direction][1]) * Math.pow(Math.exp(1), -gamma * r[i][direction]);
                    particles[i][1] += (Math.random() - 0.5) * 1;
                    if (particles[i][1]<=0) {particles[i][1] = 0.01;}
                    particles[i][2] += 1 * (particlestmp[i][2] - particlestmp[direction][2]) * Math.pow(Math.exp(1), -gamma * r[i][direction]);
                    particles[i][2] += (Math.random() - 0.5) * 2;
                    particles[i][2] = Math.round(particles[i][2]);
                    particles[i][3] += 1 * (particlestmp[i][3] - particlestmp[direction][3]) * Math.pow(Math.exp(1), -gamma * r[i][direction]);
                    particles[i][3] += (Math.random() - 0.5) * 2;
                    particles[i][3] = Math.round(particles[i][3]);
                    if (particles[i][3]<1) {particles[i][3] = 1;}
                    particles[i][4] += 1 * (particlestmp[i][4] - particlestmp[direction][4]) * Math.pow(Math.exp(1), -gamma * r[i][direction]);
                    particles[i][4] += (Math.random() - 0.5) * 3;
                    if (particles[i][4]<=0) {particles[i][4] = -1;} else {particles[i][4] = 1;}
                    
                    if (particles[i][4] == -1) {
                        particles[i][0] = alt2gravitysearch(n, S, q, c, particles[i][1], (int) particles[i][2], (int) particles[i][3]);
                    }
                    else {
                        particles[i][0] = alt2gravitysearchreverse(n, S, q, c, particles[i][1], (int) particles[i][2], (int) particles[i][3]);
                    }
                }
                else {
                    particles[i][1] += (Math.random() - 0.5) * 1;
                    if (particles[i][1]<=0) {particles[i][1] = 0.01;}
                    particles[i][2] += (Math.random() - 0.5) * 2;
                    particles[i][2] = Math.round(particles[i][2]);
                    particles[i][3] += (Math.random() - 0.5) * 2;
                    particles[i][3] = Math.round(particles[i][3]);
                    if (particles[i][3]<1) {particles[i][3] = 1;}
                    particles[i][4] += (Math.random() - 0.5) * 3;
                    if (particles[i][4]<=0) {particles[i][4] = -1;} else {particles[i][4] = 1;}
                    if (particles[i][4] == -1) {
                        particles[i][0] = alt2gravitysearch(n, S, q, c, particles[i][1], (int) particles[i][2], (int) particles[i][3]);
                    }
                    else {
                        particles[i][0] = alt2gravitysearchreverse(n, S, q, c, particles[i][1], (int) particles[i][2], (int) particles[i][3]);
                    }
                }
                
                if (bestparticle[0] > particles[i][0]) {
                    bestparticle[0] = particles[i][0];
                    bestparticle[1] = particles[i][1];
                    bestparticle[2] = particles[i][2];
                    bestparticle[3] = particles[i][3];
                    bestparticle[4] = particles[i][4];
                }
            }
            //System.out.println(bestparticle[0]);
            generations += 1;
        }
                
        //System.out.println(bestparticle[0]);
        return bestparticle[0];
    }
    
    public static double ameabesearch(int n, double S, double[] q, double[][] c, double[][] alpha, double R, int s, int t) { //RType = 1, 2, 3
        long timer = System.nanoTime();
        int[] path = new int[2*n + 1];
        double dist = 0;
        double[] charge = new double[2*n];
        double VehicleS = 0;
        double qmax=0;
        for (int i = 0; i < n; i++) {
            if (qmax<q[i]) {
                qmax=q[i];
            }
        }
        
        double VehicleCharge, AverageCharge = 0;
        for (int i = 0; i < n; i++) {
            charge[i] = q[i]/qmax;
            charge[i+n] = 0;
            AverageCharge+=charge[i];
        }
        AverageCharge/=n;
        VehicleCharge=AverageCharge*R;

        double cmax = 0;
        //System.out.println("");
        for (int i = 0; i <= 2*n; i++) {
            for (int j = 0; j <= 2*n; j++) {
                if (c[i][j]>cmax) {
                    cmax=c[i][j];
                }
            }
        }        
        
        double[][] cr2 = new double[2*n + 1][2*n + 1];
        for (int i = 0; i <= 2*n; i++) {
            for (int j = i; j <= 2*n; j++) {
                cr2[i][j]=0;
                if (c[i][j]!=0) {
                    double temp = c[i][j] / cmax;
                    cr2[i][j]=1;
                    for (int k1 = 1; k1 <= t; k1++) {cr2[i][j]*=temp;}
                    cr2[j][i]=cr2[i][j];
                }
            }
        }
        
        path[0] = 0;
        
        for (int i = 0; i<2*n; i++) {
            double MaxForce = 0; // =0 for LISA; =2*cmax for greed
            path[i + 1]=1;
            double angle = 0;
            for (int j = 1; j<=2*n; j++) {
                double Force;
                if ((path[i]!=j)&&((VehicleS + q[j - 1])>=0)&&((VehicleS + q[j - 1])<=S)) {
                    
                    double r1 = 1, r2 = 1;
                    r1 = charge[j - 1];
                    if (r1<0) {r1 *= -1;}
                    if (charge[j - 1] == 0)
                    {
                        r1 = 0;
                    }
                    else if ((charge[j - 1] == 1)||(charge[j - 1] == -1))
                    {
                        r1 = 1;
                    }
                    else if (s==0)
                    {
                        r1 = 1;
                    }
                    else if (s>0)
                    {
                        double r1t = 1;
                        for (int k1 = 1; k1 <= s; k1++) {r1t *= charge[j - 1];}
                        r1 = r1t;
                    }
                    else if (s<0)
                    {
                        double r1t = 1;
                        for (int k1 = 1; k1 <= -s; k1++) {r1t *= charge[j - 1];}
                        r1 = 1 / r1t;
                    }
                    
                    //r1 = charge[j - 1];
                    if (r1<0) {r1 *= -1;}
                    r2 = cr2[path[i]][j];
                    
                    if (j > n + 1) {
                        Force = (r1 * charge[j - 1]) / r2; // LISA
                    }
                    else {
                        Force = (VehicleCharge * r1) / r2; // LISA 1
                        //Force = (R * r1 * charge[j - 1]) / r2; // LISA 2
                    }
                    
                    //and here's the tricky part. let's start our ameabae search
                    
                    
                    if (MaxForce<Force) { //LISA
                        MaxForce=Force;
                        path[i + 1] = j;
                    }

                }
            }
            //System.out.println(i + " " + path[i + 1]);
            if (path[i + 1] > n) {
                charge[path[i + 1] - 1] = 0;
            }
            else {
                charge[path[i + 1] + n - 1] = charge[path[i + 1] - 1];
                charge[path[i + 1] - 1] = 0;
            }
            dist+=c[path[i]][path[i + 1]];
            VehicleS+=q[path[i + 1] - 1];
            //VehicleCharge=(S - VehicleS)*VehCharge; // var 2
        }
        dist+=c[path[2*n]][0];
        double elapsed = (System.nanoTime() - timer);
        /*int[] cpath = new int[2*n];
        for (int i = 0; i < 2*n; i++){
            cpath[i]=path[i + 1];
            //System.out.println(cpath[i]);
        }
        if (correct(2 * n, S, cpath, q)) {
            System.out.printf("%.5f", dist);
            System.out.print("   ");
            System.out.printf("%.5f", elapsed/1000000000);
            System.out.print("   ");
            System.out.printf("%.5f", VehCharge);
        }
        
        if (false) {
            //int[] cpath = new int[2*n];
            for (int i = 0; i < 2*n; i++){
                cpath[i]=path[i + 1];
                //System.out.println(cpath[i]);
            }
            if (correct(2 * n, S, cpath, q)) {
                System.out.print("Всё корректно");
            }
        }
        System.out.println("");*/
        return dist;
    }
    
}