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. void TRY ( int i ){
  34. 	if ( i > n ){
  35. 		// id[0] = id[1] = id[2] = id[3] = id[4] = id[5] = {-1e7 , -1e7 } ;
  36.  
  37. 		int min_euclid = 1e9 ;
  38. 		// vector < int > result ;
  39. 		int dem = 0 ;
  40.  
  41. 		for (int i = 1 ; i <= n ; i ++ )
  42. 		{
  43. 			// result.pb(x[i]) ;
  44. 			if (!id[x[i]].empty()) {
  45. 				for (int j = 0 ; j < (int)id[x[i]].size() ; j ++)
  46. 				min_euclid = min ( min_euclid , tinh_eculid ( a[i].x , a[i].y , id[x[i]][j].fir , id[x[i]][j].sec) ) ;
  47. 			}
  48. 			else { dem++ ;}
  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. 		TRY ( i + 1 ) ; 
  67. 	}
  68. }
  69. void sub1(){
  70. 	TRY(1) ;
  71. 	for (int i = 0 ; i < ans.size() ; i ++){
  72. 		cout << ans[i] << ' '; 
  73. 	}
  74. }
  75. // int b[Max_n+3] ;
  76. void sub2(){
  77. 	int id_for_fir , check = 0 ;
  78.  
  79. 	for (int i = 1 ; i <= n ; i ++ ){
  80. 		int res1 = -1e9 , res2 =  -1e9 ; 
  81. 		if ( i < n ) res1 = tinh_eculid ( a[i+1].x , a[i+1].y , a[i].x , a[i].y) ;
  82. 		if ( i < n - 1 ) res2 = tinh_eculid ( a[i+2].x , a[i+2].y , a[i].x , a[i].y) ;
  83. 		int check_now = 0 ;
  84. 		if (res1 >= res2 && res1 != -1e9 ){
  85. 			check = 1 ;
  86. 		}
  87. 		else if ( res2 != -1e9 ) check = 2 ;
  88. 		if ( max ( res1 , res2) > res){
  89. 			res = max ( res1 , res2 ) ;
  90. 			check = check_now ;
  91. 			id_for_fir = i ;
  92. 		}
  93. 	}
  94. 	// cerr << 1 << '\n';
  95. 	// int dem = 0 ;
  96. 	for (int i = 1 ; i <= n ; i ++ ){
  97. 		if ( id_for_fir != i ){
  98. 			cout << 2 << ' ' ; 
  99. 		}
  100. 		else if ( id_for_fir == i ){
  101. 			cout << 1 << ' ' ; 
  102. 			if ( check == 1 ){
  103. 				cout << 1 << ' '; i ++ ;
  104. 			}
  105. 			else {
  106. 				cout << 2 << ' ' << 1 << ' ';
  107. 				i += 2 ; 
  108. 			}
  109. 		}
  110. 	}
  111. }
  112. int b[Max_n+3] ;
  113. int cp[Max_n+3] ;
  114. int ans_1 = -1e9 ; 
  115. void sub3(){
  116. 	for (int i = 1 ; i <= n ; i ++ ){ b[i] = i ; }
  117. 		sort ( b + 1 , b + n + 1 , [&] ( int x, int y) { return a[x].x < a[y].x; }) ;
  118. 	int j = 1 ; 
  119. 	int min_euclid = 1e9 ;
  120. 	map < int , int > mp ; 
  121. 	for (int i = 1 ; i <= n ; i ++ ){
  122. 		if ( j <= m ){
  123. 			cp[b[i]] = j++ ;
  124. 			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)) ;  
  125. 			mp[j-1] = b[i] ; 
  126. 		}
  127. 		if ( j > m ) j = 1 ; 
  128. 	}
  129. 	ans_1 = min_euclid ; 
  130. 	for (int i = 1 ; i <= n ; i ++ ){
  131. 		cout << cp[i] << ' ' ;  
  132. 	}
  133. }
  134. void solve(){
  135. 	cin >> n ;
  136. 	cin >> m ; 
  137. 	for (int i = 1; i <= n ; i ++ ){
  138. 		cin >> a[i].x >> a[i].y
  139.  ;	}
  140.  	// if ( n <= 10 && m != 2){
  141.  	// 	sub1() ;
  142.  	// }
  143.  	// else if ( m == 2 ) {
  144.  	// 	// for (int i = 1 ; i <= n ; i ++ ){
  145.  	// 	// 	b[i] = i ;
  146.  	// 	// m = 2 
  147.  	// 	// thi se co 2 truong hop la 1 1 
  148.  	// 	// va 1 2 1 
  149.  	// 	// = > xem cai nao max nhat ghi la 
  150.  	// 	// sau may cai kia thi cout nhu nao cung duoc
  151.  	// 	// }
  152.  	// 	sub2() ; 
  153.  	// }
  154.  	// // else sub3();
  155.  	// sub1() ; 
  156.  	// cout << res ; 
  157.  	// cout << '\n' ;
  158.  	// sub3() ; 
  159.  	// cout << ans_1 << '\n';
  160.  	// sub 3 
  161.  	// khi y = 0 , = > sort ( lai mang x )
  162.  	// roi xem la max khi dat theo kieu 1 2 3 4 5 1 2 3 4 5 
  163.  	// dung mot cai bien id truoc khi sort 
  164.  	// khieu nhu the 
  165.  	// cout << ra ans 
  166.  	if ( n <= 10 && m != 2){
  167.  		sub1() ;
  168.  	}
  169.  	else if ( m == 2 ) {
  170.  		// for (int i = 1 ; i <= n ; i ++ ){
  171.  		// 	b[i] = i ;
  172.  		// m = 2 
  173.  		// thi se co 2 truong hop la 1 1 
  174.  		// va 1 2 1 
  175.  		// = > xem cai nao max nhat ghi la 
  176.  		// sau may cai kia thi cout nhu nao cung duoc
  177.  		// }
  178.  		sub2() ; 
  179.  	}
  180.  	else sub3();
  181. }
  182. _nhatminh{
  183. freopen("");
  184. ios_base::sync_with_stdio(0);
  185. cin.tie(0); cout.tie(0);
  186. int q=1;
  187. // cin >> q;
  188. while (q--)
  189. 	solve();
  190. cerr << '\n' << "Time elapsed " << TIME << "s.\n";
  191. return (0);
  192. }
Success #stdin #stdout #stderr 1.05s 5284KB
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 1.05119s.
https://ideone.com/2ZOTWF
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!