2015
07-16

charge-station

There are n cities in M^3′s empire. M^3 owns a palace and a car and the palace resides in city 1. One day, she wants to travel around all the cities from her palace and finally back to her home. However, her car has limited energy and can only travel by no more than D meters. Before it was run out of energy, it should be charged in some oil station. Under M^3′s despotic power, the judge is forced to build several oil stations in some of the cities. The judge must build an oil station in city 1 and building other oil stations is up to his choice as long as M^3 can successfully travel around all the cities.
Building an oil station in city i will cost 2i-1 MMMB. Please help the judge calculate out the minimum cost to build the oil stations in order to fulfill M^3′s will.

There are several test cases (no more than 50), each case begin with two integer N, D (the number of cities and the maximum distance the car can run after charged, 0 < N ≤ 128).
Then follows N lines and line i will contain two numbers x, y(0 ≤ x, y ≤ 1000), indicating the coordinate of city i.
The distance between city i and city j will be ceil(sqrt((xi – xj)2 + (yi – yj)2)). (ceil means rounding the number up, e.g. ceil(4.1) = 5)

There are several test cases (no more than 50), each case begin with two integer N, D (the number of cities and the maximum distance the car can run after charged, 0 < N ≤ 128).
Then follows N lines and line i will contain two numbers x, y(0 ≤ x, y ≤ 1000), indicating the coordinate of city i.
The distance between city i and city j will be ceil(sqrt((xi – xj)2 + (yi – yj)2)). (ceil means rounding the number up, e.g. ceil(4.1) = 5)

3 3
0 0
0 3
0 1

3 2
0 0
0 3
0 1

3 1
0 0
0 3
0 1

16 23
30 40
37 52
49 49
52 64
31 62
52 33
42 41
52 41
57 58
62 42
42 57
27 68
43 67
58 48
58 27
37 69

11
111
-1
10111011
Hint
In case 1, the judge should select (0, 0) and (0, 3) as the oil station which result in the visiting route: 1->3->2->3->1. And the cost is 2^(1-1) + 2^(2-1) = 3.


#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cmath>
//#include <conio.h>
using namespace std;
#define INF 100000000
bool mark[200];
int dis[200][200];
int N,D;
double sq(double x1,double y1,double x2,double y2){
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
bool visit[150];
int ct;
void dfs(int u){
visit[u]=true;
ct++;
for(int i=1;i<=N;i++)
if(!visit[i]&&dis[u][i]<=D){
dfs(i);
}
}
void OK(int u,int lt){
// printf("%d %d ?",u,lt);getch();
if(mark[u]){
lt=D,visit[u]=true;
ct++;
}
else{
if(lt>=(D+1)/2) visit[u]=true,ct++;
else return;
}
for(int i=1;i<=N;i++)
if(u!=i&&!visit[i]&&dis[u][i]<=lt)
OK(i,lt-dis[u][i]);

}

int main(){

int rc[200][2];
int i,j;
while(scanf("%d %d",&N,&D)!=EOF){
//memset(mark,0,sizeof(mark));
for(i=1;i<=N;i++) mark[i]=true;
for(i=1;i<=N;i++)
scanf("%d %d",&rc[i][0],&rc[i][1]);
if(N==1){printf("0\n");continue;}
for(i=1;i<N;i++)
for(j=i+1;j<=N;j++){
double t=sq(rc[i][0],rc[i][1],rc[j][0],rc[j][1]);
int ti=ceil(sqrt(t));
dis[i][j]=dis[j][i]=ti;
}
memset(visit,0,sizeof(visit));
ct=0;
dfs(1);
if(ct<N) {printf("-1\n");continue;}
for(i=N;i>1;i--){
mark[i]=false;
ct=0;
memset(visit,0,sizeof(visit));
OK(1,0);
if(ct<N)
mark[i]=true;
//  printf("\n");
}
for(i=N;i>0;i--)if(mark[i]) break;
for(;i>0;i--) if(mark[i])printf("1");else printf("0");
printf("\n");
}
return 0;
}