fork download
copy 
  1. /*
  2. written by- Piyush Golani
  3. language- c++
  4. country- India
  5. College- N.I.T Jamshedpur
  6. */
  7. #include <cmath>
  8. #include <ctime>
  9. #include <iostream>
  10. #include <string>
  11. #include <vector>
  12. #include<cstdio>
  13. #include<sstream>
  14. #include<algorithm>
  15. #include<cstdlib>
  16. #include<cstring>
  17. #include<map>
  18. #include<set>
  19. #include<queue>
  20. #include<cctype>
  21. using namespace std;
  22. #define pb push_back
  23. #define all(s) s.begin(),s.end()
  24. #define f(i,a,b) for(int i=a;i<b;i++)
  25. #define F(i,a,b) for(int i=a;i>=b;i--)
  26. #define PI 3.1415926535897932384626433832795
  27. #define INF 2000000000
  28. #define BIG_INF 7000000000000000000LL
  29. #define mp make_pair
  30. #define eps 1e-9
  31. #define si(n) scanf("%d",&n)
  32. #define sll(n) scanf("%lld",&n)
  33. #define mod 1000000007
  34. #define mm 10000000
  35. #define pd pair<double,int>
  36.  
  37. typedef long long LL;
  38.  
  39.  
  40. string inttostring(int n)
  41. {
  42.     stringstream a;
  43.     a<<n;
  44.     return a.str();
  45. }
  46.  
  47. int stringtoint(string A)
  48. {
  49.     istringstream a(A);
  50.     int p;
  51.     a>>p;
  52.     return p;
  53. }
  54.  
  55. //////////////////////////////////////////////////////
  56.  
  57. class KingdomXCitiesandVillagesAnother {
  58. public:
  59.    double determineLength( vector <int> cityX, vector <int> cityY, vector <int> villageX, vector <int> villageY ) {
  60.     int c=cityX.size();
  61.     int v=villageX.size();
  62.     int nodes=c+v;
  63.     double w[nodes][nodes];
  64.     f(i,0,c)
  65.     {
  66.         f(j,0,v)
  67.         {
  68.             w[i][c+j]=sqrt((LL)(cityX[i]-villageX[j])*(cityX[i]-villageX[j])+(LL)(cityY[i]-villageY[j])*(cityY[i]-villageY[j]));
  69.             w[c+j][i]=w[i][c+j];
  70.         }
  71.     }
  72.     f(i,0,v)
  73.     {
  74.         f(j,0,v)
  75.         {
  76.             w[c+i][c+j]=sqrt((LL)(villageX[i]-villageX[j])*(villageX[i]-villageX[j])+(LL)(villageY[i]-villageY[j])*(villageY[i]-villageY[j]));
  77.             w[c+j][c+i]=w[c+i][c+j];
  78.         }
  79.     }
  80.     priority_queue<pd,vector<pd>,greater<pd> > PQ;
  81.     bool visited[nodes];
  82.     memset(visited,false,sizeof(visited));
  83.     f(i,0,c)
  84.     visited[i]=true;
  85.     f(i,0,c)
  86.     {
  87.         f(j,0,v)
  88.         {
  89.             PQ.push(mp(w[i][c+j],c+j));
  90.         }
  91.     }
  92.     double res=0;
  93.     while(!PQ.empty())
  94.     {
  95.         pd ytk=PQ.top();
  96.         PQ.pop();
  97.         if(visited[ytk.second]) continue;
  98.         res+=ytk.first;
  99.         visited[ytk.second]=true;
  100.         f(i,0,nodes) if(!visited[i]) PQ.push(mp(w[ytk.second][i],i));
  101.     }
  102.     return res;
  103.    }
  104. };
  105.  
  106. // BEGIN CUT HERE
  107. namespace moj_harness {
  108.     int run_test_case(int);
  109. 	void run_test(int casenum = -1, bool quiet = false) {
  110. 		if (casenum != -1) {
  111. 			if (run_test_case(casenum) == -1 && !quiet) {
  112. 				cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
  113. 			}
  114. 			return;
  115. 		}
  116.  
  117. 		int correct = 0, total = 0;
  118. 		for (int i=0;; ++i) {
  119. 			int x = run_test_case(i);
  120. 			if (x == -1) {
  121. 				if (i >= 100) break;
  122. 				continue;
  123. 			}
  124. 			correct += x;
  125. 			++total;
  126. 		}
  127.  
  128. 		if (total == 0) {
  129. 			cerr << "No test cases run." << endl;
  130. 		} else if (correct < total) {
  131. 			cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
  132. 		} else {
  133. 			cerr << "All " << total << " tests passed!" << endl;
  134. 		}
  135. 	}
  136.  
  137. 	static const double MAX_DOUBLE_ERROR = 1e-9; static bool topcoder_fequ(double expected, double result) { if (isnan(expected)) { return isnan(result); } else if (isinf(expected)) { if (expected > 0) { return result > 0 && isinf(result); } else { return result < 0 && isinf(result); } } else if (isnan(result) || isinf(result)) { return false; } else if (fabs(result - expected) < MAX_DOUBLE_ERROR) { return true; } else { double mmin = min(expected * (1.0 - MAX_DOUBLE_ERROR), expected * (1.0 + MAX_DOUBLE_ERROR)); double mmax = max(expected * (1.0 - MAX_DOUBLE_ERROR), expected * (1.0 + MAX_DOUBLE_ERROR)); return result > mmin && result < mmax; } }
  138. 	double moj_relative_error(double expected, double result) { if (isnan(expected) || isinf(expected) || isnan(result) || isinf(result) || expected == 0) return 0; return fabs(result-expected) / fabs(expected); }
  139.  
  140. 	int verify_case(int casenum, const double &expected, const double &received, clock_t elapsed) {
  141. 		cerr << "Example " << casenum << "... ";
  142.  
  143. 		string verdict;
  144. 		vector<string> info;
  145. 		char buf[100];
  146.  
  147. 		if (elapsed > CLOCKS_PER_SEC / 200) {
  148. 			sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
  149. 			info.push_back(buf);
  150. 		}
  151.  
  152. 		if (topcoder_fequ(expected, received)) {
  153. 			verdict = "PASSED";
  154. 			double rerr = moj_relative_error(expected, received);
  155. 			if (rerr > 0) {
  156. 				sprintf(buf, "relative error %.3e", rerr);
  157. 				info.push_back(buf);
  158. 			}
  159. 		} else {
  160. 			verdict = "FAILED";
  161. 		}
  162.  
  163. 		cerr << verdict;
  164. 		if (!info.empty()) {
  165. 			cerr << " (";
  166. 			for (int i=0; i<(int)info.size(); ++i) {
  167. 				if (i > 0) cerr << ", ";
  168. 				cerr << info[i];
  169. 			}
  170. 			cerr << ")";
  171. 		}
  172. 		cerr << endl;
  173.  
  174. 		if (verdict == "FAILED") {
  175. 			cerr << "    Expected: " << expected << endl;
  176. 			cerr << "    Received: " << received << endl;
  177. 		}
  178.  
  179. 		return verdict == "PASSED";
  180. 	}
  181.  
  182. 	int run_test_case(int casenum__) {
  183. 		switch (casenum__) {
  184. 		case 0: {
  185. 			int cityX[]               = {1};
  186. 			int cityY[]               = {1};
  187. 			int villageX[]            = {2,3};
  188. 			int villageY[]            = {1,1};
  189. 			double expected__         = 2.0;
  190.  
  191. 			clock_t start__           = clock();
  192. 			double received__         = KingdomXCitiesandVillagesAnother().determineLength(vector <int>(cityX, cityX + (sizeof cityX / sizeof cityX[0])), vector <int>(cityY, cityY + (sizeof cityY / sizeof cityY[0])), vector <int>(villageX, villageX + (sizeof villageX / sizeof villageX[0])), vector <int>(villageY, villageY + (sizeof villageY / sizeof villageY[0])));
  193. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  194. 		}
  195. 		case 1: {
  196. 			int cityX[]               = {1,2};
  197. 			int cityY[]               = {1,1};
  198. 			int villageX[]            = {1,2};
  199. 			int villageY[]            = {2,2};
  200. 			double expected__         = 2.0;
  201.  
  202. 			clock_t start__           = clock();
  203. 			double received__         = KingdomXCitiesandVillagesAnother().determineLength(vector <int>(cityX, cityX + (sizeof cityX / sizeof cityX[0])), vector <int>(cityY, cityY + (sizeof cityY / sizeof cityY[0])), vector <int>(villageX, villageX + (sizeof villageX / sizeof villageX[0])), vector <int>(villageY, villageY + (sizeof villageY / sizeof villageY[0])));
  204. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  205. 		}
  206. 		case 2: {
  207. 			int cityX[]               = {0};
  208. 			int cityY[]               = {0};
  209. 			int villageX[]            = {2};
  210. 			int villageY[]            = {2};
  211. 			double expected__         = 2.8284271247461903;
  212.  
  213. 			clock_t start__           = clock();
  214. 			double received__         = KingdomXCitiesandVillagesAnother().determineLength(vector <int>(cityX, cityX + (sizeof cityX / sizeof cityX[0])), vector <int>(cityY, cityY + (sizeof cityY / sizeof cityY[0])), vector <int>(villageX, villageX + (sizeof villageX / sizeof villageX[0])), vector <int>(villageY, villageY + (sizeof villageY / sizeof villageY[0])));
  215. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  216. 		}
  217.  
  218. 		// custom cases
  219.  
  220. /*      case 3: {
  221. 			int cityX[]               = ;
  222. 			int cityY[]               = ;
  223. 			int villageX[]            = ;
  224. 			int villageY[]            = ;
  225. 			double expected__         = ;
  226.  
  227. 			clock_t start__           = clock();
  228. 			double received__         = KingdomXCitiesandVillagesAnother().determineLength(vector <int>(cityX, cityX + (sizeof cityX / sizeof cityX[0])), vector <int>(cityY, cityY + (sizeof cityY / sizeof cityY[0])), vector <int>(villageX, villageX + (sizeof villageX / sizeof villageX[0])), vector <int>(villageY, villageY + (sizeof villageY / sizeof villageY[0])));
  229. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  230. 		}*/
  231. /*      case 4: {
  232. 			int cityX[]               = ;
  233. 			int cityY[]               = ;
  234. 			int villageX[]            = ;
  235. 			int villageY[]            = ;
  236. 			double expected__         = ;
  237.  
  238. 			clock_t start__           = clock();
  239. 			double received__         = KingdomXCitiesandVillagesAnother().determineLength(vector <int>(cityX, cityX + (sizeof cityX / sizeof cityX[0])), vector <int>(cityY, cityY + (sizeof cityY / sizeof cityY[0])), vector <int>(villageX, villageX + (sizeof villageX / sizeof villageX[0])), vector <int>(villageY, villageY + (sizeof villageY / sizeof villageY[0])));
  240. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  241. 		}*/
  242. /*      case 5: {
  243. 			int cityX[]               = ;
  244. 			int cityY[]               = ;
  245. 			int villageX[]            = ;
  246. 			int villageY[]            = ;
  247. 			double expected__         = ;
  248.  
  249. 			clock_t start__           = clock();
  250. 			double received__         = KingdomXCitiesandVillagesAnother().determineLength(vector <int>(cityX, cityX + (sizeof cityX / sizeof cityX[0])), vector <int>(cityY, cityY + (sizeof cityY / sizeof cityY[0])), vector <int>(villageX, villageX + (sizeof villageX / sizeof villageX[0])), vector <int>(villageY, villageY + (sizeof villageY / sizeof villageY[0])));
  251. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  252. 		}*/
  253. 		default:
  254. 			return -1;
  255. 		}
  256. 	}
  257. }
  258.  
  259.  
  260. int main(int argc, char *argv[]) {
  261. 	if (argc == 1) {
  262. 		moj_harness::run_test();
  263. 	} else {
  264. 		for (int i=1; i<argc; ++i)
  265. 			moj_harness::run_test(atoi(argv[i]));
  266. 	}
  267. }
  268. // END CUT HERE
  269.  
  270.  
  271.  
Success #stdin #stdout 0s 3044KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hFisCo
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!