Points on Plane
Problem's Link
Mean:
在二维坐标中给定n个点，求一条哈密顿通路。
analyse:
一开始忽略了“无需保证路径最短”这个条件，一直在套最短哈密顿通路的模板，无限TLE。
简单的构造，首先对x坐标设一个阀值，分段输出，从下到上、再从上到下、在从下到上...直到所有点输出完为止。
当然也可横向扫描输出。
Time complexity: O(N)
Source code:
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-09-11-16.00
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);
const int N = 1010;
int n;
vector < pair < int , int > > X [N ];
vector < int > res;
int main()
{
scanf( "%d" , &n);
for( int i = 0; i <n; ++ i)
{
int x , y;
scanf( "%d %d" , & x , & y);
X [ x / 1000 ]. push_back( make_pair( y , i));
}
for( int i = 0; i <= 1000; ++ i)
{
sort( X [ i ]. begin (), X [ i ]. end());
if( i & 1)
reverse( X [ i ]. begin (), X [ i ]. end());
for( auto & it: X [ i ])
printf( "%d " , 1 + it . second);
}
return 0;
}
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-09-11-16.00
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);
const int N = 1010;
int n;
vector < pair < int , int > > X [N ];
vector < int > res;
int main()
{
scanf( "%d" , &n);
for( int i = 0; i <n; ++ i)
{
int x , y;
scanf( "%d %d" , & x , & y);
X [ x / 1000 ]. push_back( make_pair( y , i));
}
for( int i = 0; i <= 1000; ++ i)
{
sort( X [ i ]. begin (), X [ i ]. end());
if( i & 1)
reverse( X [ i ]. begin (), X [ i ]. end());
for( auto & it: X [ i ])
printf( "%d " , 1 + it . second);
}
return 0;
}
