学习心得(code)

superlong@CoreCoder

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  74 Posts :: 0 Stories :: 5 Comments :: 0 Trackbacks

公告

文字可能放在http://blog.csdn.net/superlong100,此处存放代码

常用链接

留言簿(4)

我参与的团队

搜索

  •  

最新随笔

最新评论

  • 1. re: Poj 1279
  • 对于一个凹多边形用叉积计算面积 后能根据结果的正负来判断给的点集的时针方向?
  • --bsshanghai
  • 2. re: Poj 3691
  • 你写的这个get_fail() 好像并是真正的get_fail,也是说fail指向的串并不是当前结点的子串。为什么要这样弄呢?
  • --acmer1183
  • 3. re: HDU2295[未登录]
  • 这个是IDA* 也就是迭代加深@ylfdrib
  • --superlong
  • 4. re: HDU2295
  • 评论内容较长,点击标题查看
  • --ylfdrib
  • 5. re: HOJ 11482
  • 呵呵..把代码发在这里很不错..以后我也试试...百度的编辑器太烂了....
  • --csuft1

阅读排行榜

评论排行榜

#include <stdio.h>
#include 
<stdlib.h>
#include 
<string.h>

const int N = 55;
const double eps = 1e-7;
const int SIZE = N*N;

int n, m , k;
int L[SIZE], R[SIZE], U[SIZE], D[SIZE], Sum[SIZE], Row[SIZE], Col[SIZE];
int lenx, id, deep, anslen;
bool OK;

inline 
int rd() {
    
char ch;
    
while( ch = getchar(), ch == ' ' || ch == '\n');
    
int d = ch - '0';
    
while( ch = getchar(), ch <= '9' && ch >= '0' ) d = d* 10 + ch - '0';
    
return d;
}

struct point {
    
int x, y;
    
void read() {
        x 
= rd(); y = rd();
    }
} city[N], radar[N];

struct circle {
    point o;
    
double r;
    circle(){}
    circle(point _o, 
double _r) {
        o 
= _o;
        r 
= _r;
    }
    
bool incircle(point q) {
        
return 1.0*(o.x-q.x)*(o.x-q.x) + 1.0*(o.y-q.y)*(o.y-q.y) - r * r < eps;
    }
} Radar[N];

void init() {
    n 
= rd(); m = rd(); k = rd();
    
for(int i = 1; i <= n; i ++) city[i].read();
    
for(int i = 1; i <= m; i ++) Radar[i].o.read();
}

inline 
void pre(int cntcol) {
    
for(int i = 0; i <= cntcol; i ++) {
        L[i] 
= i - 1;
        R[i] 
= i + 1;
        U[i] 
= D[i] = i;
        Sum[i] 
= 0;
    }
    L[
0= cntcol; R[cntcol] = 0;
    id 
= cntcol + 1;
}

inline 
void insert(int i, int *xx) {
    
for(int j = 0; j < lenx; j ++, id ++) {
        
int x = xx[j];
        Row[id] 
= i;
        Col[id] 
= x;
        Sum[x] 
++;
        U[id] 
= x;
        D[id] 
= D[x];
        U[D[x]] 
= id;
        D[x] 
= id;
        
if( j == 0 ) {
            L[id] 
= R[id] = id;
        } 
else {
            L[id] 
= id - 1;
            R[id] 
= id - j;
            R[id
-1= id;
            L[id
-j] = id;
        }
    }
}


inline 
void remove(int &c) {
    
for(int i = D[c]; i != c ; i = D[i]) {
        L[R[i]] 
= L[i];
        R[L[i]] 
= R[i];
    }
}
inline 
void resume(int &c) {
    
for(int i = U[c]; i != c ; i = U[i]) {
        L[R[i]] 
= i;
        R[L[i]] 
= i;
    }
}

inline 
int Astar() {
    
int res = 0;
    
bool vis[N*N] = {false};
    
for(int i = R[0]; i != 0; i =R[i]) {
        
if!vis[ i ] ) {
            vis[ i ] 
= true;
            res 
++;
            
for(int j = D[i]; j != i; j = D[j]) {
                
for(int k = R[j]; k != j; k = R[k]) {
                    vis[ Col[k] ] 
= true;
                }
            }
        }
    }
    
return res;
}

void dfs(int dep) {
    
if( Astar() + dep > deep )    return ;
    
if(R[0== 0)    {
        anslen 
= dep;     
        OK 
= true;
        
return;
    }
    
int idx = R[0];
    
for(int i = R[0] ; i != 0 ; i = R[i]) {
        
if(Sum[i] < Sum[idx]) {
            idx 
= i;
            
if( Sum[idx] <= 1 ) break;
        }
    }
    
for(int i = D[idx] ; i != idx; i = D[i]) {
        remove(i);
        
for(int j = R[i] ; j != i ; j = R[j]) remove(j);
        dfs( dep 
+ 1 );
        
for(int j = L[i] ; j != i ; j = L[j]) resume(j);
        resume(i);
        
if( OK ) return;
    }
}

inline 
void build() {
    
int x[N];
    
for(int i = 1; i <= m; i ++) {
        lenx 
= 0;
        
for(int j = 1; j <= n; j ++) {
            
if( Radar[i].incircle(city[j]) ) {
                x[lenx
++= j;
            }
        }
        insert(i, x);
    }
}

bool check(double R) {
    
for(int i = 1; i <= m; i ++) Radar[i].r = R;
    pre(n);
    build();
    deep 
= 0;
    anslen 
= 0;
    OK 
= false;
    
while!OK ) {
        
if( deep > k )  break;
        dfs(
0);
        deep 
++;
    }
    
return OK;
}

void solve() {
    
double left = 0, right = 1e29, mid;
    
while( right - left > eps) {
        mid 
= (left + right) / 2;
        
if( check(mid) ) {
            right 
= mid;
        } 
else {
            left 
= mid;
        }
    }
    printf(
"%lf\n", left);
    
}

int main() {
    
int t;
    scanf(
"%d"&t);
    
while( t -- ) {
        init();
        solve();
    }
}

posted on 2010-08-16 11:07 superlong 阅读(585) 评论(2)  编辑 收藏 引用

Feedback

# re: HDU2295 2010-10-02 10:50 ylfdrib
在你的check函数里,为什么要用while呢
while( !OK ) {
if( deep > k ) break;
dfs(0);
deep ++;
}

不是直接dfs就可以了么。。,表示不懂

还有Astar的返回值有什么含义。。 请指教。。  回复  更多评论
  

# re: HDU2295[未登录] 2010-10-04 22:38 superlong
这个是IDA* 也就是迭代加深@ylfdrib
  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理