fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define _nhatminh  int main()
  3. #define ll long long
  4. #define str string
  5. #define fir first
  6. #define sec second
  7. #define ld long double
  8. #define pb push_back
  9. #define MOD 100000009
  10. #define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define piint pair < int , int >
  13. #define piL pair < int , ll>
  14. #define pLL pair < ll , ll >
  15. #define TIME (1.0*clock()/CLOCKS_PER_SEC)
  16. using namespace std;
  17. const int Max_n=1000;
  18. // int x ;
  19. // piint id[5 + 3 ] ;
  20. int tinh_eculid (int x , int y , int x1 , int y1) {
  21. 	return sqrt ( ( x - x1) * ( x - x1) + ( y - y1 ) * ( y - y1 ) ) ;  
  22. }
  23. int x[Max_n+3] ;
  24. int res = -1e9 ; 
  25. std::vector<int > ans ;
  26. 	int n ; int m ;
  27. 	struct phandinhphongxa
  28. 	 {
  29. 	 	int x , y ;
  30. 	 }; 
  31. 	 phandinhphongxa a[Max_n+3];
  32. 		vector < piint > id[6] ;
  33. 	int kt[5+1] ;
  34. void TRY ( int i ,int dem ) {
  35. 	if ( i > n ){
  36. 		// id[0] = id[1] = id[2] = id[3] = id[4] = id[5] = {-1e7 , -1e7 } ;
  37.  
  38. 		int min_euclid = 1e9 ;
  39. 		// vector < int > result ;
  40. 		// int dem = 0 ;
  41. 		if ( dem < m ) return ; 
  42. 		for (int i = 1 ; i <= n ; i ++ )
  43. 		{
  44. 			// result.pb(x[i]) ;
  45. 			if (!id[x[i]].empty()) {
  46. 				for (int j = 0 ; j < (int)id[x[i]].size() ; j ++)
  47. 				min_euclid = min ( min_euclid , tinh_eculid ( a[i].x , a[i].y , id[x[i]][j].fir , id[x[i]][j].sec) ) ;
  48. 			}
  49. 			id[x[i]].pb(make_pair( a[i].x , a[i].y) );
  50. 		}
  51. 		for (int i = 1 ;i <= m ; i ++ ) {
  52. 			id[i].clear() ; 
  53. 		}
  54. 		if ( dem < m ){
  55. 			return ;
  56. 		}
  57. 		if ( min_euclid > res ){ 
  58. 			res = min_euclid ; 
  59. 			ans.clear() ;
  60. 			for (int i = 1 ; i <= n ; i ++ ) ans.pb(x[i]);
  61. 		}
  62. 		return ;
  63. 	}
  64. 	for (int j = 1 ; j <= m ; j ++){
  65. 		x[i] = j ;
  66. 		kt[j]++;
  67. 		int new_dem = dem ; 
  68. 		if ( kt[j] == 1 ) new_dem ++ ;
  69. 		TRY ( i + 1 ,new_dem) ; 
  70. 		kt[j]--;
  71. 	}
  72. }
  73. void sub1(){
  74. 	TRY(1, 0 ) ;
  75. 	for (int i = 0 ; i < ans.size() ; i ++){
  76. 		cout << ans[i] << ' '; 
  77. 	}
  78. }
  79. // int b[Max_n+3] ;
  80. void sub2(){
  81. 	int id_for_fir , check = 0 ;
  82.  
  83. 	for (int i = 1 ; i <= n ; i ++ ){
  84. 		int res1 = -1e9 , res2 =  -1e9 ; 
  85. 		if ( i < n ) res1 = tinh_eculid ( a[i+1].x , a[i+1].y , a[i].x , a[i].y) ;
  86. 		if ( i < n - 1 ) res2 = tinh_eculid ( a[i+2].x , a[i+2].y , a[i].x , a[i].y) ;
  87. 		int check_now = 0 ;
  88. 		if (res1 >= res2 && res1 != -1e9 ){
  89. 			check = 1 ;
  90. 		}
  91. 		else if ( res2 != -1e9 ) check = 2 ;
  92. 		if ( max ( res1 , res2) > res){
  93. 			res = max ( res1 , res2 ) ;
  94. 			check = check_now ;
  95. 			id_for_fir = i ;
  96. 		}
  97. 	}
  98. 	// cerr << 1 << '\n';
  99. 	// int dem = 0 ;
  100. 	for (int i = 1 ; i <= n ; i ++ ){
  101. 		if ( id_for_fir != i ){
  102. 			cout << 2 << ' ' ; 
  103. 		}
  104. 		else if ( id_for_fir == i ){
  105. 			cout << 1 << ' ' ; 
  106. 			if ( check == 1 ){
  107. 				cout << 1 << ' '; i ++ ;
  108. 			}
  109. 			else {
  110. 				cout << 2 << ' ' << 1 << ' ';
  111. 				i += 2 ; 
  112. 			}
  113. 		}
  114. 	}
  115. }
  116. int b[Max_n+3] ;
  117. int cp[Max_n+3] ;
  118. int ans_1 = -1e9 ; 
  119. void sub3(){
  120. 	for (int i = 1 ; i <= n ; i ++ ){ b[i] = i ; }
  121. 		sort ( b + 1 , b + n + 1 , [&] ( int x, int y) { return a[x].x < a[y].x; }) ;
  122. 	int j = 1 ; 
  123. 	int min_euclid = 1e9 ;
  124. 	map < int , int > mp ; 
  125. 	for (int i = 1 ; i <= n ; i ++ ){
  126. 		if ( j <= m ){
  127. 			cp[b[i]] = j++ ;
  128. 			if ( mp[j-1] != 0 ) min_euclid = min ( min_euclid , tinh_eculid (a[mp[j-1]].x , a[mp[j-1]].y , a[b[i]].x , a[b[i]].y)) ;  
  129. 			mp[j-1] = b[i] ; 
  130. 		}
  131. 		if ( j > m ) j = 1 ; 
  132. 	}
  133. 	ans_1 = min_euclid ; 
  134. 	for (int i = 1 ; i <= n ; i ++ ){
  135. 		cout << cp[i] << ' ' ;  
  136. 	}
  137. }
  138. void solve(){
  139. 	cin >> n ;
  140. 	cin >> m ; 
  141. 	for (int i = 1; i <= n ; i ++ ){
  142. 		cin >> a[i].x >> a[i].y
  143.  ;	}
  144.  	// if ( n <= 10 && m != 2){
  145.  	// 	sub1() ;
  146.  	// }
  147.  	// else if ( m == 2 ) {
  148.  	// 	// for (int i = 1 ; i <= n ; i ++ ){
  149.  	// 	// 	b[i] = i ;
  150.  	// 	// m = 2 
  151.  	// 	// thi se co 2 truong hop la 1 1 
  152.  	// 	// va 1 2 1 
  153.  	// 	// = > xem cai nao max nhat ghi la 
  154.  	// 	// sau may cai kia thi cout nhu nao cung duoc
  155.  	// 	// }
  156.  	// 	sub2() ; 
  157.  	// }
  158.  	// // else sub3();
  159.  	// sub1() ; 
  160.  	// cout << res ; 
  161.  	// cout << '\n' ;
  162.  	// sub3() ; 
  163.  	// cout << ans_1 << '\n';
  164.  	// sub 3 
  165.  	// khi y = 0 , = > sort ( lai mang x )
  166.  	// roi xem la max khi dat theo kieu 1 2 3 4 5 1 2 3 4 5 
  167.  	// dung mot cai bien id truoc khi sort 
  168.  	// khieu nhu the 
  169.  	// cout << ra ans 
  170.  	if ( n <= 10 && m != 2){
  171.  		sub1() ;
  172.  	}
  173.  	else if ( m == 2 ) {
  174.  		// for (int i = 1 ; i <= n ; i ++ ){
  175.  		// 	b[i] = i ;
  176.  		// m = 2 
  177.  		// thi se co 2 truong hop la 1 1 
  178.  		// va 1 2 1 
  179.  		// = > xem cai nao max nhat ghi la 
  180.  		// sau may cai kia thi cout nhu nao cung duoc
  181.  		// }
  182.  		sub2() ; 
  183.  	}
  184.  	else sub3();
  185. }
  186. _nhatminh{
  187. freopen("");
  188. ios_base::sync_with_stdio(0);
  189. cin.tie(0); cout.tie(0);
  190. int q=1;
  191. // cin >> q;
  192. while (q--)
  193. 	solve();
  194. cerr << '\n' << "Time elapsed " << TIME << "s.\n";
  195. return (0);
  196. }
Success #stdin #stdout #stderr 0.53s 5280KB
comments (?)
stdin
copy 
10 5
1 0
-9 0
8 0
2 0
3 0
5 0
-5 0
-6 0
7 0
4 0
stdout
copy 
1 1 2 2 3 4 2 3 1 5
stderr
copy 
Time elapsed 0.52958s.
https://ideone.com/5EGAVG
language:
C++14 (gcc 8.3)
created:
14 days 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!