/* * vim: ts=4 sw=4 et tw=0 wm=0 * * libvpsc - A solver for the problem of Variable Placement with * Separation Constraints. * * Copyright (C) 2005-2008 Monash University * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library in the file LICENSE; if not, * write to the Free Software Foundation, Inc., 59 Temple Place, * Suite 330, Boston, MA 02111-1307 USA * */ #include #include #include #include #include #include #include #include #include using namespace std; using namespace vpsc; inline double getRand(double range) { return range*rand()/RAND_MAX; } void printRects(vector &rs) { printf("Set of %d rectangles:\n",(int)rs.size()); for(unsigned i=0;i &rs) { rs.resize(n); static double const rect_size = 5; static double const min_rect_size = 1e-4; static double const fld_size = sqrt(rect_size * n / 2.0); double coords[4]; for (unsigned i = 0; i < n; ++i) { for (unsigned d = 0; d < 2; ++d) { //unsigned const end = 1 + (rand() % (fld_size - 1)); //unsigned const start = rand() % end; double const start = getRand(fld_size); double const end = start + min_rect_size + getRand(rect_size); coords[2 * d] = start; coords[2 * d + 1] = end; } rs[i]=new Rectangle(coords[0],coords[1],coords[2],coords[3]); } } vector& generateRects(double coords[][4], unsigned n,vector& rs) { rs.resize(n); for (unsigned i = 0; i < n; ++i) { rs[i]=new Rectangle(coords[i][0],coords[i][1],coords[i][2],coords[i][3]); } return rs; } void test(vector &rs, double &cost, double &duration) { unsigned n=rs.size(); vector ors(n); for (unsigned i = 0; i < n; ++i) { ors[i]=new Rectangle(rs[i]->getMinX(),rs[i]->getMaxX(),rs[i]->getMinY(),rs[i]->getMaxY()); } clock_t starttime = clock(); removeoverlaps(rs); duration = (double)(clock() - starttime)/CLOCKS_PER_SEC; cost = 0; for(unsigned i=0;igetCentreX()-ors[i]->getCentreX(); double dy=rs[i]->getCentreY()-ors[i]->getCentreY(); cost+=sqrt(dx*dx+dy*dy); delete rs[i]; delete ors[i]; } } double test1[][4]={ { 0, 50, 0, 30 }, { 10, 20, 10, 29 }, { 30, 70, 39, 70 }, { 0, 90, 40, 50 }, { 30, 70, 1, 29 } }; unsigned n1=5; double test2[][4]={ { 7, 22, 39, 54 }, { 7, 33, 0, 59 }, { 3, 26, 16, 56 }, { 7, 17, 18, 20 }, { 1, 59, 11, 26 }, { 19, 20, 13, 49 }, { 1, 10, 0, 4 }, { 47, 52, 1, 3 } }; unsigned n2=8; double test3[][4]={ { 8, 32, 29, 36 }, { 19, 24, 2, 27 }, { 4, 5, 27, 55 }, { 6, 7, 13, 26 }, { 3, 39, 46, 62 }, { 6, 23, 2, 19 }, { 18, 39, 5, 23 }, { 35, 63, 42, 78 }, { 16, 18, 14, 72 }, { 12, 32, 10, 58 } }; unsigned n3=10; double test4[][4]={ { 315.755, 355.288, 353.595, 449.627 }, { 395.048, 395.635, 253.943, 362.228 }, { 254.439, 393.289, 278.708, 286.346 }, { 209.852, 370.831, 326.496, 507.255 }, { 271.947, 415.74, 362.228, 450.318 }, { 293.408, 405.197, 220.61, 244.119 }, { 276.482, 386.472, 286.346, 435.767 }, { 268.211, 436.23, 192.807, 220.61 }, { 378.008, 502.118, 358.437, 475.587 }, { 340.68, 472.597, 249.492, 335.448 } }; unsigned n4=10; double test5[][4]={ { 7, 22, 39, 54 }, { 7, 33, 0, 59 }, { 3, 26, 16, 56 }, { 7, 17, 18, 20 }, { 1, 59, 11, 26 }, { 19, 20, 13, 49 }, { 1, 10, 0, 4 }, { 47, 52, 1, 3 } }; unsigned n5=8; double test6[][4]={ { 40, 69, 63, 69 }, { 1, 5, 27, 64 }, { 34, 66, 20, 22 }, { 1, 24, 10, 25 }, { 1, 19, 9, 61 }, { 0, 56, 8, 70 }, { 33, 35, 13, 28 }, { 11, 31, 33, 35 }, { 12, 22, 3, 23 } }; unsigned n6=9; double test7[][4]={ { 341.594, 388.459, 373.491, 518.168 }, { 271.214, 324.782, 311.332, 409.166 }, { 293.848, 475.064, 305.194, 391.162 }, { 255.317, 447.738, 342.671, 489.923 }, { 228.375, 261.057, 206.422, 327.794 }, { 383.552, 462.834, 363.132, 412.843 }, { 288.859, 481.054, 351.895, 497.728 }, { 201.307, 368.511, 387.02, 394.95 }, { 257.961, 259.673, 386.503, 518.403 }, { 200.178, 275.606, 364.968, 466.787 } }; unsigned n7=10; double test8[][4]={{12.807,15.7566,14.9478,16.7924}, {7.76228,11.6532,4.75249,4.75349}, {7.84596,10.1387,15.465,16.7709}, {1.80748,3.0357,5.9983,6.16279}, {6.46447,7.47249,12.8694,13.4378}, {14.0026,17.3342,5.10141,9.81088}, {6.84223,6.85932,6.40395,9.21135}, {7.63462,10.3552,6.78124,8.59953}, {0.26429,2.80847,14.5724,17.7455}, {14.7686,15.7148,3.46036,5.66776}, {10.635,11.4893,12.5044,16.941}, {6.32027,10.7117,14.2953,15.6276}, {11.9942,13.1118,10.6893,11.4477}, {11.9384,15.1357,2.20982,6.92982}, {2.89395,4.29002,11.7058,16.2896}, {9.44116,12.7547,9.75556,11.1811}, {5.2475,8.00607,15.3652,17.026}, {2.09541,3.76981,2.5526,3.16739}, {3.14595,6.66351,10.3007,14.4881}, {4.88109,9.38044,9.02416,10.2954}, {7.55378,9.14715,13.9686,16.0468}, {1.70299,5.42198,14.1913,14.2191}, {14.4877,14.4897,6.14013,8.50074}, {12.9909,14.5163,10.322,12.4457}, {11.616,12.0848,3.7601,5.45419}, {10.3087,13.358,3.04666,3.53389}, {2.28263,2.44881,13.806,15.8206}, {3.31805,5.47662,3.91187,6.85355}, {0.484138,2.06164,3.57335,7.87753}, {4.73784,5.12359,9.383,11.9217}, {12.2921,12.7769,12.329,12.8139}, {12.7351,16.7141,12.7658,13.78}, {3.71614,5.79872,1.53137,4.97126}, {10.7423,14.8183,2.57104,2.94168}, {9.93995,10.1557,1.3432,1.499}, {0.198099,0.204966,9.29459,11.8795}, {14.1043,18.8473,11.2028,14.1971}, {4.23857,4.95743,14.7047,17.1439}, {13.936,15.9612,10.7744,14.8598}, {11.355,15.6824,2.49113,5.96963}, {12.8528,16.3913,3.82582,6.67259}, {13.9445,14.7354,10.8576,12.9503}, {13.0041,15.6166,2.07035,3.70034}, {2.31809,5.03195,1.13659,5.8604}, {10.2454,14.5396,10.9442,15.4321}, {7.12259,11.3929,7.20864,10.4059}, {6.54862,9.88399,1.82828,5.89899}, {4.27072,7.52613,7.99016,11.1703}, {8.84828,9.15453,10.1489,11.7934}, {7.71027,8.97206,3.26462,4.02636}, {14.3383,15.1727,3.02586,3.26268}, {9.21233,11.1919,13.9814,16.1433}, {13.1946,16.1613,12.2268,13.1319}, {13.0462,15.6689,7.03513,8.59752}, {8.72724,11.3859,5.69193,7.8238}, {10.6241,14.1033,7.88946,9.95327}, {8.48376,10.8714,8.86955,11.2137}, {3.55633,4.14351,13.7308,18.4988}, {1.79802,4.68843,11.0964,11.6543}, {13.1535,14.6895,1.52144,2.50643}, {1.24533,4.27261,13.345,13.4925}, {14.4031,18.7944,15.4447,18.0096}, {8.56933,11.3392,0.446787,1.18762}, {11.311,16.0574,8.41,8.76508}, {13.5332,17.8479,8.2067,11.4446}, {5.73826,6.63581,10.8364,11.6186}, {10.1995,11.5202,6.54248,9.49804}, {14.6456,16.7915,7.01621,7.57531}, {15.1444,16.4184,1.45761,2.35577}, {11.8169,12.0382,14.8149,19.3316}, {10.148,11.1227,15.0087,18.1595}, {10.9498,14.7849,12.3852,13.9467}, {10.7631,10.9141,5.24419,8.64319}, {11.2486,12.6029,6.25029,10.0076}, {12.8731,16.0703,4.96619,8.54006}, {6.92828,8.53172,8.36509,11.8971}, {3.1677,7.20423,14.5582,17.1794}, {14.1426,16.9327,15.1198,19.1306}, {2.52943,6.64027,5.18935,8.58545}, {6.89613,11.4515,3.7672,6.23813}, {2.91428,6.40636,1.4231,4.10552}, {9.81892,12.9687,8.25114,10.1775}, {14.6192,14.7412,10.8349,15.1725}, {6.96657,11.7009,11.0638,11.8966}, {7.03182,9.20687,2.04293,2.60462}, {7.47955,9.28533,7.45213,8.37318}, {6.24651,9.79246,8.61803,9.91034}, {4.73642,7.48461,9.59481,12.748}, {8.70644,11.1702,2.54172,4.26587}, {14.9028,19.4109,6.238,8.04256}, {5.22907,8.45899,1.98714,4.94042}, {8.96884,12.3636,1.72663,3.39844}, {6.96563,8.04735,10.6198,11.3663}, {1.65099,5.65883,10.5002,13.9039}, {11.3337,11.5138,5.31369,7.75029}, {2.79561,4.08151,7.04269,9.00167}}; unsigned n8=96; double test9[][4]={{2.67865,4.81342,8.67025,11.5025}, {5.77912,6.94355,9.80043,12.2904}, {11.9459,13.8675,3.66967,7.38408}, {6.72663,8.30474,3.37566,7.24571}, {9.2081,10.9827,10.9557,11.8868}, {0.161903,3.31202,3.35371,3.84933}, {4.46508,9.18934,9.43037,10.9125}, {3.84059,5.2565,8.66868,8.70713}, {4.67598,5.15207,5.2252,8.92099}, {1.19252,1.31215,7.97481,8.27191}, {4.57641,5.71063,0.440628,4.17365}, {6.80268,11.5523,3.78375,4.79819}, {11.2172,13.7652,8.44876,11.1649}, {11.4673,13.1644,6.09156,7.41026}, {12.2995,13.585,0.155239,4.63887}, {12.3513,15.3947,8.3437,11.1337}, {3.92566,6.15611,12.432,16.3993}, {12.6351,14.6039,9.96391,13.1152}, {0.682894,2.48867,7.66904,8.86704}, {3.50189,7.28939,8.37741,8.96276}, {2.37719,4.19762,11.1129,12.0465}, {5.53568,8.1444,11.9056,15.5818}, {7.32876,11.2713,12.1655,15.0785}, {2.534,6.15563,9.30845,11.2833}, {8.00852,12.8051,2.16786,4.90262}, {11.8095,12.814,11.5818,13.7731}, {7.54398,9.23043,7.36953,10.7315}, {8.36918,9.83071,11.8668,11.8776}, {5.72267,9.66642,1.46379,3.71362}, {11.2725,14.6538,4.76772,7.30304}, {5.8638,10.7623,5.99865,10.0994}, {11.0224,12.6455,0.852638,2.20201}, {4.03151,8.51056,6.12449,10.3672}, {7.75136,10.6782,10.648,11.8606}, {11.9663,14.3993,2.83154,5.46437}, {6.05275,8.00044,10.9675,15.3426}, {10.9702,13.146,8.98465,12.4718}, {4.99665,7.91376,9.19241,9.71153}, {3.7422,4.00542,2.00556,2.53918}, {9.01679,10.9439,12.8107,15.1367}, {10.0117,11.5009,0.194049,3.08568}, {8.29117,13.1323,6.99045,8.65707}, {5.97395,10.5816,5.77559,7.35126}, {5.68856,6.51699,4.40392,5.82242}, {0.209729,3.89072,7.36013,8.98447}, {0.360264,1.88558,0.319886,3.22738}, {2.02163,2.07428,3.2753,8.12958}, {5.05075,5.86987,12.7958,16.7689}, {10.6484,15.5931,7.23546,10.4741}, {7.20998,7.46939,2.44384,5.10459}, {12.5022,15.1819,10.6593,13.5708}, {2.3619,2.45407,5.75168,7.28966}, {12.131,16.661,4.39608,8.19289}, {9.81023,10.731,6.67919,9.31523}, {6.97712,10.166,8.4813,13.3432}, {6.45378,7.44457,8.96504,11.9806}, {8.70396,11.5729,7.15588,12.1524}, {9.93058,14.0306,0.849502,1.80855}, {8.32174,8.34616,7.52595,12.0431}, {2.79979,5.93358,4.90296,7.6893}, {0.72484,5.42439,3.48229,5.77743}, {6.05275,10.2779,7.4252,7.72184}, {4.41176,6.91184,11.8809,15.3923}, {6.50435,8.04432,11.4826,15.3172}, {12.16,14.3518,1.13763,4.17255}, {7.82506,10.5124,8.05713,9.03876}}; unsigned n9=66; double test10[][4]={{15.9875,18.9768,15.3193,17.9811}, {16.5669,19.7216,1.05824,1.58667}, {8.80629,9.88527,9.71101,13.2142}, {19.568,20.1767,3.28922,8.03561}, {13.6363,15.6827,12.9329,16.6542}, {2.32913,3.58085,8.28597,12.6503}, {6.86597,11.2847,5.9172,10.236}, {8.57413,11.0048,18.0203,18.4095}, {7.68828,8.89193,9.52038,12.3945}, {13.5784,15.499,0.824193,4.7533}, {5.70392,8.26946,10.1955,12.8184}, {17.9857,22.6483,14.2013,16.0377}, {14.7965,16.4222,11.9332,16.5984}, {20.5111,23.1383,0.355473,0.834461}, {5.88763,9.2761,8.31995,11.6173}, {13.8307,16.6334,17.2376,19.8715}, {7.20005,8.99179,19.0137,23.483}, {3.67112,6.97933,18.6142,21.1208}, {0.936183,5.81945,5.11063,7.47703}, {9.85383,12.4861,7.80027,11.677}, {8.07584,11.1964,13.8571,17.9736}, {8.07017,10.0661,8.42816,9.79417}, {10.8259,11.6232,16.7028,19.3248}, {18.55,19.3911,17.174,22.0082}, {1.34073,1.93538,17.9341,20.4509}, {11.7558,12.1994,0.295703,2.19289}, {12.4063,13.662,0.965124,5.21391}, {2.2033,2.85518,16.4455,20.0191}, {6.3853,9.77239,0.892142,2.17773}, {0.546736,5.29679,12.1949,15.2469}, {14.1365,17.5213,14.7027,15.1512}, {9.46879,11.9145,11.8539,14.4408}, {8.49611,8.98075,17.1388,17.5066}, {1.53577,2.52014,0.615943,4.13396}, {7.12078,9.05901,20.3739,23.44}, {2.7104,7.09713,16.4442,20.8587}, {12.9707,14.2845,12.5642,16.2281}, {13.5086,14.3207,17.7611,20.1056}, {19.2264,24.1481,2.063,5.27645}, {15.2016,18.2491,1.10228,3.37286}, {16.7733,18.1385,2.35807,7.0123}, {19.8272,21.9464,18.27,22.8376}, {4.27133,8.48869,19.5925,21.488}, {19.6951,23.7284,10.5207,11.1889}, {0.799027,3.61863,1.42504,3.44902}, {1.31871,5.95584,16.4147,18.2479}, {19.8398,21.0495,15.2495,15.8842}, {3.15773,5.76599,11.1562,12.2007}, {4.61422,4.78559,16.6607,16.9497}, {11.0064,11.5745,16.521,19.5463}, {13.3865,15.7969,12.215,14.3112}, {0.272424,4.59201,7.19502,9.58004}, {15.6377,16.4926,18.5978,19.0178}, {1.44957,1.65985,5.24023,10.1284}, {0.0559948,0.138395,3.75354,4.46554}, {3.24015,3.86196,12.205,14.0543}, {2.64686,3.51587,16.1429,16.6103}, {2.56003,5.14236,5.6624,8.31491}, {13.7143,16.5806,7.32777,10.6354}, {15.8994,20.4036,0.171759,0.567584}, {11.1247,11.5263,7.61341,8.80042}, {10.7869,11.8353,7.73861,8.39933}, {16.7563,18.1604,15.6377,20.3633}, {4.7627,5.87556,0.850618,4.25755}, {11.2178,15.6734,14.2378,15.9026}, {2.00323,5.94744,1.78428,4.77571}, {16.0705,20.0359,9.50528,12.9563}, {14.9808,18.3586,9.56819,10.8817}, {13.7005,17.173,10.5755,15.5172}, {6.24185,6.44174,11.9766,16.0609}, {14.0767,16.1476,11.9904,14.2274}, {18.3009,20.9378,0.109473,0.330122}, {0.395109,4.35458,19.8694,23.5078}, {17.4949,22.4626,6.16132,10.5268}, {0.992178,2.11099,18.813,22.5419}, {8.41369,12.6754,20.0682,22.6}, {19.5239,23.6359,3.22945,3.81068}, {6.60361,6.84761,11.8174,12.6899}, {8.95351,9.96275,11.2373,12.3269}, {13.8414,17.1229,18.182,20.7568}, {13.0468,17.4872,16.8349,21.2615}, {16.6053,17.1026,5.24778,8.1272}, {1.20043,2.96974,10.1904,13.8153}, {7.73924,7.74809,1.53703,3.76274}, {15.0915,18.4866,18.6576,18.9426}, {10.69,13.9811,6.92511,9.44625}, {8.66032,12.8382,6.67974,9.08735}, {3.24707,3.91176,7.21641,8.75134}, {20.5281,23.518,5.04016,5.38868}, {8.78238,13.6922,11.9149,12.334}, {19.1358,19.5264,15.9157,16.8192}, {4.52551,7.52884,12.1049,16.4566}, {18.467,22.8957,2.97024,7.48362}, {17.9618,18.9449,2.7601,4.06645}, {10.8057,15.3718,7.7254,8.32173}, {19.6416,21.5781,7.62473,11.5731}, {5.14712,8.87694,0.495145,1.50088}, {4.11719,6.22953,3.59814,8.25023}, {6.34314,9.83141,1.90886,3.52039}, {11.6041,11.7642,12.6177,16.2647}, {17.4351,19.786,0.846214,2.85357}, {7.90974,12.4031,10.5818,10.868}, {3.33578,5.53021,19.271,22.6137}, {14.3296,18.1074,3.76864,6.21134}, {1.39798,4.21194,14.7015,18.9814}, {13.3463,13.89,4.76333,8.78979}, {7.78517,12.3834,12.0445,12.1204}, {1.21553,4.14149,10.9523,11.5827}, {10.7328,15.0635,11.2248,16.0148}, {1.89816,6.42421,6.21479,9.51491}, {5.76369,9.87896,0.471237,2.08597}, {1.10543,3.50571,6.4243,6.85217}, {13.4916,16.9187,13.4167,14.751}, {6.61683,9.79075,4.44435,7.2165}, {17.5276,21.8159,3.22316,7.12862}, {8.09408,10.3727,0.167984,1.77021}, {8.04815,12.6168,7.91666,11.0816}, {1.32248,2.63905,12.5164,17.4845}, {7.324,11.7358,9.05354,13.7152}, {15.0274,18.5751,11.55,13.6444}, {15.3627,16.1478,19.7391,21.3528}, {16.5701,19.0741,18.0876,18.9877}, {19.9719,20.1289,10.2999,14.2899}, {5.77124,9.49847,20.3551,23.9988}, {9.4065,13.7029,1.45775,2.17524}, {8.22117,12.8533,16.9079,17.5996}, {8.20293,12.4012,15.7691,15.783}, {9.33037,11.8253,0.286895,2.70091}, {12.5114,14.6471,11.0241,13.8678}, {14.6423,15.2091,5.08987,9.29257}, {10.4729,12.308,1.7717,6.27227}, {9.65187,11.9638,14.3196,18.937}, {5.1704,6.94718,18.4884,22.8028}, {4.66015,8.43071,12.6095,14.2635}, {19.5384,21.1589,7.47562,10.9592}, {20.3595,24.407,0.804689,2.94465}, {0.775119,2.53222,1.35017,2.38185}, {14.1459,18.0717,13.111,17.3643}, {15.9535,16.9371,3.47482,6.36462}, {15.1727,17.7769,13.1324,16.2993}, {17.2678,19.5719,19.2912,23.3942}, {14.5832,17.1443,19.2559,24.0751}, {1.57289,3.42857,7.75497,11.9183}, {2.63994,5.18274,5.84108,8.64802}, {7.56056,8.51991,0.284378,0.750091}, {8.4225,12.0985,13.1443,16.5509}, {12.4397,13.7349,16.1177,21.0089}, {18.411,22.1179,12.4302,16.1478}, {16.7343,19.9381,0.87138,4.38391}, {0.729191,5.0941,0.4316,3.36382}, {7.96699,10.079,15.0613,19.489}, {14.4215,16.2705,13.932,15.6623}, {9.37756,12.4608,12.8857,16.6014}, {12.0729,12.5163,2.59841,7.39714}, {7.52658,11.0203,15.2853,19.805}, {16.0919,20.3462,13.6464,15.1218}, {6.17075,10.0034,17.5729,21.8258}, {8.94533,11.0185,7.98461,12.5047}, {0.249775,1.8787,2.72361,7.6554}, {11.5167,11.8826,8.7937,10.8008}, {14.3038,17.8052,19.0873,20.7193}, {19.7272,24.1131,5.29434,7.64106}, {19.7624,20.0966,13.2827,17.354}, {5.58186,7.99298,3.3987,5.8269}, {19.7479,20.3262,16.1492,17.465}, {3.25902,6.3684,17.0948,20.9851}, {12.7549,14.4322,1.40931,6.02218}, {12.232,13.2567,0.559319,3.07481}, {0.138414,4.75571,14.9273,18.2745}, {6.04241,6.23422,9.62104,10.3701}}; unsigned n10=170; double test11[][4]={{2.20847,5.99613,25.7684,29.5065}, {4.38169,7.14163,-7.79499,-7.42678}, {17.1816,19.4476,-5.03151,-3.38153}, {10.6383,11.0169,-0.356332,3.85003}, {13.3309,15.7634,21.4146,24.0122}, {17.1354,20.5384,27.9053,29.8839}, {4.82128,7.88931,4.90792,5.71239}, {13.1802,14.7891,24.0123,26.5035}, {9.1468,9.95493,-3.73661,-1.29955}, {14.4021,17.8989,19.2669,23.5805}, {3.53936,4.95206,17.2632,19.2913}, {11.2732,15.3951,10.4298,11.6976}, {9.82902,13.9892,17.9523,19.9811}, {10.0265,11.0793,16.4791,17.5196}, {1.27427,5.64116,7.85316,8.33764}, {3.70992,7.16293,5.06311,6.98578}, {9.95501,13.9876,-3.13412,-1.29965}, {17.6086,21.8963,15.3022,17.9743}, {2.05607,2.66477,-0.552748,0.286511}, {12.6971,13.3533,-4.23798,-3.73671}, {7.7961,11.69,7.35371,11.9837}, {7.68167,9.93012,1.7933,3.98514}, {1.2176,2.27018,0.286611,3.17168}, {4.98578,7.91342,12.8464,16.1781}, {16.5918,21.3527,4.59687,5.72758}, {9.12809,9.56481,1.38197,2.061}, {14.6904,19.1649,-3.38143,-1.21492}, {11.3046,15.5357,14.6315,17.2819}, {3.69836,4.52282,5.06311,5.67974}, {12.2713,13.7058,11.6977,14.6314}, {0.130993,3.26738,-4.32728,-3.7221}, {11.4317,12.3544,19.9812,22.2083}, {10.0298,10.1041,11.1483,12.7055}, {16.2023,16.7313,1.49517,4.59677}, {12.4149,15.8265,4.33334,6.45789}, {17.575,19.9519,12.3124,15.3021}, {17.0991,22.0233,3.78959,6.02599}, {3.99216,5.32933,0.583351,0.882127}, {16.5929,18.003,14.3823,17.6574}, {13.5273,15.1372,16.4791,20.1285}, {12.3687,15.2044,6.45799,7.83514}, {8.04258,9.47375,17.3137,21.5515}, {7.329,10.9322,7.65703,11.5161}, {1.98895,2.89459,1.84656,3.17168}, {0.520521,2.46608,6.71895,10.4866}, {13.184,16.1474,6.45799,7.30869}, {2.13915,4.58689,17.2632,19.8192}, {15.8375,18.2786,15.9558,18.1255}, {14.7223,16.4109,16.4791,17.3636}, {4.00206,7.29287,-4.32728,-1.41062}, {16.6028,18.6157,14.6315,17.1786}, {3.19495,7.10528,-1.41052,0.583251}, {1.69626,5.11997,0.326338,1.84646}, {12.1579,12.759,-0.356332,0.328198}, {3.51735,7.12098,5.71249,7.85306}, {0.953512,5.10372,3.17178,5.06301}, {13.2737,14.3319,18.7924,21.1975}, {1.46188,5.99876,10.3471,12.8463}, {8.39195,9.77825,1.66426,2.061}, {1.81344,5.57851,-3.53802,0.326238}, {1.31773,2.99152,29.5066,33.3419}, {5.33625,7.15652,19.4265,19.8527}, {0.432492,3.44635,7.60608,10.3589}, {1.60933,2.36115,-1.16144,0.286511}, {9.27774,10.4284,-1.86525,-1.56998}, {11.8878,13.7671,-5.11518,-4.23808}, {10.0073,10.2574,11.282,12.9297}, {10.5778,11.703,0.629406,0.965262}, {3.17349,7.96657,16.1782,17.2631}, {11.2281,13.6998,12.2002,12.4339}, {13.7166,18.3124,19.2669,21.4145}, {10.5388,15.0813,0.328298,4.33324}, {9.05987,12.0136,-1.29945,-0.356432}, {6.74526,7.05518,-8.26859,-7.79509}, {17.7736,20.6859,5.72768,8.29825}, {2.22113,7.1491,21.4284,25.7683}, {16.1247,17.7842,2.70437,3.3773}, {8.34023,10.0276,13.9827,18.7779}, {15.1872,18.2348,17.1787,17.2902}, {16.5308,17.6299,6.45799,8.71682}, {5.98601,9.22204,23.2905,26.0581}, {7.64095,10.7424,18.778,22.0208}, {15.0585,19.52,17.7993,19.2668}, {17.646,20.037,0.451228,3.78949}, {0.0160052,1.94859,4.68464,6.71885}, {7.29434,9.17489,13.9827,17.3136}, {17.7896,21.639,6.02609,9.48842}, {4.43065,8.71164,19.8528,23.2904}, {16.5231,21.0708,3.3774,4.59677}, {14.2096,16.0172,17.282,17.9522}, {8.32648,9.09478,3.98524,7.65693}, {3.6703,7.6841,0.583351,4.90782}, {9.90605,10.9591,11.5162,13.1508}, {14.7669,18.5129,-1.21482,3.3773}, {3.48104,6.74301,29.5066,30.5551}, {9.22657,10.4539,-5.59946,-1.29955}, {8.12181,8.34154,-2.11601,1.66416}, {4.11375,5.37752,30.5552,34.3283}, {9.11434,12.5991,8.88212,10.4297}, {11.3365,14.9133,-8.77796,-4.9549}, {15.7809,16.0235,-2.30357,0.667869}, {15.4629,16.7224,4.59687,6.45789}, {13.3766,16.7042,21.4146,25.1652}, {7.87643,10.2361,12.8464,13.9826}, {7.38842,11.7536,11.5162,16.479}, {5.15799,9.74446,-7.42668,-4.32738}, {16.0009,16.044,-3.82308,0.667869}, {15.6318,18.7733,8.71692,11.607}, {10.7258,12.2305,7.30879,8.88202}, {8.17133,9.84923,-1.56988,1.38187}, {3.5179,5.38762,0.583351,5.06301}, {9.4516,10.8319,22.0209,26.7891}, {9.94456,11.8221,19.9812,21.2926}, {5.14479,8.31779,3.92878,7.65693}, {14.6057,18.2633,0.667969,4.59677}, {5.62784,8.67939,17.3137,19.4264}, {10.9244,13.5481,-1.29955,-1.29945}, {5.76759,6.30746,-3.722,-3.5131}, {7.13259,9.6258,8.33774,11.5161}, {1.05144,1.32443,10.359,10.9074}, {16.4807,19.9127,26.5036,27.9052}, {5.9629,7.66553,-1.41052,-1.14028}, {13.6489,16.9728,22.2084,25.5279}, {2.50777,4.43837,19.8193,21.4283}, {1.57577,3.7409,15.383,18.2258}, {17.1816,18.8466,17.2903,17.7992}, {8.43156,13.0154,-4.9548,-3.13422}, {1.88827,6.19077,6.98588,10.347}, {14.73,15.2147,17.9523,18.7923}, {5.55742,8.69305,2.0611,3.92868}}; unsigned n11=130; double test12[][4]={ {4.92744,6.6604,4.27234,8.301}, {1.54924,2.51053,4.48526,9.19033}, {1.55587,5.56226,-0.660563,3.35611}, {1.87055,2.251,3.56944,6.75421}, {1.58179,2.94863,5.24022,8.78858}, {1.88069,5.98638,3.94188,5.24012}, {1.81447,5.62383,5.24022,9.22211}, {4.06842,6.37182,-0.053975,3.94178}, {4.03643,4.2387,3.35621,3.94178}, {1.16362,3.67328,0.29063,3.01001}, }; unsigned n12=10; int main() { double c,t; vector rs; cout << "test1" << endl; test(generateRects(test1,n1,rs),c,t); cout << "test2" << endl; test(generateRects(test2,n2,rs),c,t); cout << "test3" << endl; test(generateRects(test3,n3,rs),c,t); cout << "test4" << endl; test(generateRects(test4,n4,rs),c,t); cout << "test5" << endl; test(generateRects(test5,n5,rs),c,t); cout << "test6" << endl; test(generateRects(test6,n6,rs),c,t); cout << "test7" << endl; test(generateRects(test7,n7,rs),c,t); cout << "test8" << endl; test(generateRects(test8,n8,rs),c,t); cout << "test9" << endl; test(generateRects(test9,n9,rs),c,t); cout << "test10" << endl; test(generateRects(test10,n10,rs),c,t); cout << "test11" << endl; test(generateRects(test11,n11,rs),c,t); cout << "test12" << endl; test(generateRects(test12,n12,rs),c,t); int max_size=100, repeats=100,step=10; //srand(time(NULL)); for(int i=10;i<=max_size;i+=step) { //if(i%5==0) cout << i << endl; double disp=0, time=0; for(int repeat=repeats;repeat--;) { vector rs; generateRandomRects(i,rs); //printRects(rs); test(rs,c,t); disp+=c; time+=t; } disp/=repeats; time/=repeats; cout << i << "," << time << "," << disp << endl; } return 0; }