月度归档：2013年11月

[POJ 1200]

字符串hash

很基本的hash题目，现在做这种程度的题10分钟就敲完1A了。整个程序都是模块化的，思路也能很自然地延伸。

#include<cstdio>
#include<cstring>

#define MAXP 100003

int n,nc,hd[MAXP],el,sl,ans;
char s[16000001];

struct E
{
    int i,p;
}e[16000000];

inline void adde(int hs,int i)
{
    e[el].i=i; e[el].p=hd[hs]; hd[hs]=el++;
}

void init()
{
    memset(hd,-1,sizeof hd);
    el=ans=0;
    sl=strlen(s);
}

int bkdr(char *s,char *e)
{
    int hs=0;
    while(s!=e)
        hs=(hs*131+*s++)%MAXP;
    return hs;
}

int fi(int hs,int i)
{
    int j,k,l;
    for(l=hd[hs];l!=-1;l=e[l].p)
    {
        j=e[l].i;
        for(k=0;k<n&&s[i+k]==s[j+k];k++);
        if(k==n)
            return 1;
    }
    return 0;
}

void solve()
{
    int i,j,k,l;
    for(i=0;i+n<=sl;i++)
    {
        j=bkdr(s+i,s+i+n);
        if(!fi(j,i))
        {
            adde(j,i);
            ans++;
        }
    }
    printf("%d\n",ans);
}

int main()
{
    while(~scanf("%d%d%s",&n,&nc,s))
    {
        init();
        solve();
    }
    return 0;
}

#include<cstdio>

#include<cstring>

#define MAXP 100003

int n,nc,hd[MAXP],el,sl,ans;

char s[16000001];

struct E

{

int i,p;

}e[16000000];

inline void adde(int hs,int i)

{

e[el].i=i; e[el].p=hd[hs]; hd[hs]=el++;

}

void init()

{

memset(hd,-1,sizeof hd);

el=ans=0;

sl=strlen(s);

}

int bkdr(char *s,char *e)

{

int hs=0;

while(s!=e)

hs=(hs*131+*s++)%MAXP;

return hs;

}

int fi(int hs,int i)

{

int j,k,l;

for(l=hd[hs];l!=-1;l=e[l].p)

{

j=e[l].i;

for(k=0;k<n&&s[i+k]==s[j+k];k++);

if(k==n)

return 1;

}

return 0;

}

void solve()

{

int i,j,k,l;

for(i=0;i+n<=sl;i++)

{

j=bkdr(s+i,s+i+n);

if(!fi(j,i))

{

adde(j,i);

ans++;

}

printf("%d\n",ans);

}

int main()

{

while(~scanf("%d%d%s",&n,&nc,s))

{

init();

solve();

}

return 0;

}

[POJ 1421]

发表回复

Peter’s Calculator

模拟（难）

给出一段程序，要求按照给定的运行方式，对每次PRINT操作判断是否有效，若有效还需求值。

并没有太多算法的题目，但各种细节很多

大致思路就是先将全部程序文本读入，进行预处理：记录每行程序的类型（赋值、打印或重置），并且
（1）如果是赋值，则对被赋值的变量进行编号，并将等号右边的内容以纯文本方式保存下来
（2）如果是打印，则检查被打印的变量之前是否存在相应赋值，若有则记录变量编号，若无则记录编号为-1
（3）如果是重置，无需特殊处理

然后就是求解了，按顺序对每行i进行处理，期间维护一个搜索赋值语句的上下界[es,ee]，初始es=ee=0，并且
（1）如果是赋值，忽略
（2）如果是打印，则ee=i-1，并尝试对该变量求值，若成功则打印值，否则打印”UNDEF”
（3）如果是重置，则es=i+1

每次对变量id求值的操作可能涉及其他变量，因此使用递归结构。而要防止循环求值，因此初始化全0数组st[]来记录变量是否在递归栈中。每次递归内部结构大致如下：
（1）若st[id]!=0，直接返回；st[id]=1，按从后往前(从ee到es)的顺序找第一个对va赋值的语句
（2）对将赋值字符串中的所有变量调用递归求值，若某变量求值失败，直接返回
（3）用一个新字符串保存将赋值字符串中所有变量替换为值后的结果（必须不修改原来的赋值字符串），随后使用递归下降分析求解该字符串的值
（4）记录变量的值，st[id]=2

最后求值完毕后，若要打印的变量st[]为2，则表示成功求值。

程序的主要部分想清楚后实现也花了不少时间，最后则是在空格问题上卡了很久。

#include<cstdio>
#include<cstring>
#define MAXL 1000

int el,sl,st[MAXL],v[MAXL],es,ee,ti;

char s[MAXL][MAXL],t[MAXL];

struct E
{
    int ins,id;
    char s[MAXL];
}e[MAXL];

int exp();

int gi(int b)
{
    int i;
    for(i=0;i<sl&&strcmp(s[i],t);i++);
    if(i==sl)
    {
        if(b)
            strcpy(s[sl++],t);
        else
            i=-1;
    }
    return i;
}

int fact()
{
    while(t[ti]&&t[ti]==' ')
        ti++;
    int d;
    if(t[ti]=='(')
    {
        ti++;
        d=exp();
        while(t[ti]!=')')
            ti++;
        ti++;
        return d;
    }
    sscanf(t+ti,"%d",&d);
    if(t[ti]&&t[ti]=='-')
        ti++;
    while(t[ti]&&t[ti]>='0'&&t[ti]<='9')
        ti++;
    return d;
}

int term()
{
    while(t[ti]&&t[ti]==' ')
        ti++;
    int d=fact();
    while(t[ti])
    {
        while(t[ti]&&t[ti]==' ')
            ti++;
        if(!t[ti]||t[ti]!='*')
            break;
        ti++;
        d*=fact();
    }
    return d;
}

int exp()
{
    while(t[ti]&&t[ti]==' ')
        ti++;
    int d=term();
    while(t[ti])
    {
        while(t[ti]&&t[ti]==' ')
            ti++;
        if(!t[ti]||t[ti]!='+'&&t[ti]!='-')
            break;
        ti++;
        if(t[ti-1]=='+')
            d+=term();
        else
            d-=term();
    }
    return d;
}

void vl(int id)
{
    if(st[id]!=0)
        return;
    st[id]=1;
    int i,j,k,rl;
    char r[MAXL];
    for(i=ee-1;i>=es;i--)
    {
        if(e[i].ins==1&&e[i].id==id)
            break;
    }
    if(i<es)
        return;
    memset(r,0,sizeof r);
    for(j=rl=0;e[i].s[j];)
    {
        if(e[i].s[j]=='('||e[i].s[j]==')'||e[i].s[j]==' '||
                e[i].s[j]=='+'||e[i].s[j]=='-'||e[i].s[j]=='*')
        {
            r[rl++]=e[i].s[j++];
        }
        else if(e[i].s[j]=='-'||e[i].s[j]>='0'&&e[i].s[j]<='9')
        {
            r[rl++]=e[i].s[j++];
            while(e[i].s[j]&&e[i].s[j]>='0'&&e[i].s[j]<='9')
            {
                r[rl++]=e[i].s[j++];
            }
        }
        else
        {
            for(k=j;e[i].s[k]>='a'&&e[i].s[k]<='z'
                    ||e[i].s[k]>='A'&&e[i].s[k]<='Z'
                    ||e[i].s[k]>='0'&&e[i].s[k]<='9';k++)
                t[k-j]=e[i].s[k];
            t[k-j]=0;
            k=gi(0);
            if(k==-1)
                return;
            vl(k);
            if(st[k]!=2)
                return;
            sprintf(r+rl,"%d",v[k]);
            while(r[rl])
                rl++;
            while(e[i].s[j]&&(e[i].s[j]>='a'&&e[i].s[j]<='z'
                    ||e[i].s[j]>='A'&&e[i].s[j]<='Z'
                    ||e[i].s[j]>='0'&&e[i].s[j]<='9'))
                j++;
        }
    }
    memcpy(t,r,sizeof t);
    ti=0;
    v[id]=exp();
    st[id]=2;
}

void init()
{
    while(~scanf("%s",t))
    {
        if(!strcmp(t,"PRINT"))
        {
            e[el].ins=2;
            scanf("%s",t);
            e[el].id=gi(0);
        }
        else if(!strcmp(t,"RESET"))
        {
            e[el].ins=3;
        }
        else
        {
            for(ti=1;t[ti]&&!(t[ti-1]==':'&&t[ti]=='=');ti++);
            if(!t[ti])
            {
                e[el].ins=1;
                e[el].id=gi(1);
                scanf("%s",t);
                if(!strcmp(t,":="))
                    gets(e[el].s);
                else
                    strcpy(e[el].s,t+2);
            }
            else
            {
                strcpy(e[el].s,t+ti+1);
                t[ti-1]=0;
                e[el].ins=1;
                e[el].id=gi(1);
            }
        }
        el++;
    }
}

void solve()
{
    int i;
    for(i=0;i<el;i++)
    {
        if(e[i].ins==2)
        {
            if(e[i].id==-1)
            {
                puts("UNDEF");
                continue;
            }
            memset(st,0,sizeof st);
            ee=i;
            vl(e[i].id);
            if(st[e[i].id]<2)
                puts("UNDEF");
            else
                printf("%d\n",v[e[i].id]);
        }
        else if(e[i].ins==3)
        {
            es=i+1;
        }
    }
}

int main()
{
    init();
    solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

#include<cstdio>

#include<cstring>

#define MAXL 1000

int el,sl,st[MAXL],v[MAXL],es,ee,ti;

char s[MAXL][MAXL],t[MAXL];

struct E

{

int ins,id;

char s[MAXL];

}e[MAXL];

int exp();

int gi(int b)

{

int i;

for(i=0;i<sl&&strcmp(s[i],t);i++);

if(i==sl)

{

if(b)

strcpy(s[sl++],t);

else

i=-1;

}

return i;

}

int fact()

{

while(t[ti]&&t[ti]==' ')

ti++;

int d;

if(t[ti]=='(')

{

ti++;

d=exp();

while(t[ti]!=')')

ti++;

return d;

}

sscanf(t+ti,"%d",&d);

if(t[ti]&&t[ti]=='-')

ti++;

while(t[ti]&&t[ti]>='0'&&t[ti]<='9')

ti++;

return d;

}

int term()

{

while(t[ti]&&t[ti]==' ')

ti++;

int d=fact();

while(t[ti])

{

while(t[ti]&&t[ti]==' ')

ti++;

if(!t[ti]||t[ti]!='*')

break;

ti++;

d*=fact();

}

return d;

}

int exp()

{

while(t[ti]&&t[ti]==' ')

ti++;

int d=term();

while(t[ti])

{

while(t[ti]&&t[ti]==' ')

ti++;

if(!t[ti]||t[ti]!='+'&&t[ti]!='-')

break;

ti++;

if(t[ti-1]=='+')

d+=term();

else

d-=term();

}

return d;

}

void vl(int id)

{

if(st[id]!=0)

return;

st[id]=1;

int i,j,k,rl;

char r[MAXL];

for(i=ee-1;i>=es;i--)

{

if(e[i].ins==1&&e[i].id==id)

break;

}

if(i<es)

return;

memset(r,0,sizeof r);

for(j=rl=0;e[i].s[j];)

{

if(e[i].s[j]=='('||e[i].s[j]==')'||e[i].s[j]==' '||

e[i].s[j]=='+'||e[i].s[j]=='-'||e[i].s[j]=='*')

{

r[rl++]=e[i].s[j++];

}

else if(e[i].s[j]=='-'||e[i].s[j]>='0'&&e[i].s[j]<='9')

{

r[rl++]=e[i].s[j++];

while(e[i].s[j]&&e[i].s[j]>='0'&&e[i].s[j]<='9')

{

r[rl++]=e[i].s[j++];

}

else

{

for(k=j;e[i].s[k]>='a'&&e[i].s[k]<='z'

||e[i].s[k]>='A'&&e[i].s[k]<='Z'

||e[i].s[k]>='0'&&e[i].s[k]<='9';k++)

t[k-j]=e[i].s[k];

t[k-j]=0;

k=gi(0);

if(k==-1)

return;

vl(k);

if(st[k]!=2)

return;

sprintf(r+rl,"%d",v[k]);

while(r[rl])

rl++;

while(e[i].s[j]&&(e[i].s[j]>='a'&&e[i].s[j]<='z'

||e[i].s[j]>='A'&&e[i].s[j]<='Z'

||e[i].s[j]>='0'&&e[i].s[j]<='9'))

j++;

}

memcpy(t,r,sizeof t);

ti=0;

v[id]=exp();

st[id]=2;

}

void init()

{

while(~scanf("%s",t))

{

if(!strcmp(t,"PRINT"))

{

e[el].ins=2;

scanf("%s",t);

e[el].id=gi(0);

}

else if(!strcmp(t,"RESET"))

{

e[el].ins=3;

}

else

{

for(ti=1;t[ti]&&!(t[ti-1]==':'&&t[ti]=='=');ti++);

if(!t[ti])

{

e[el].ins=1;

e[el].id=gi(1);

scanf("%s",t);

if(!strcmp(t,":="))

gets(e[el].s);

else

strcpy(e[el].s,t+2);

}

else

{

strcpy(e[el].s,t+ti+1);

t[ti-1]=0;

e[el].ins=1;

e[el].id=gi(1);

}

el++;

}

void solve()

{

int i;

for(i=0;i<el;i++)

{

if(e[i].ins==2)

{

if(e[i].id==-1)

{

puts("UNDEF");

continue;

}

memset(st,0,sizeof st);

ee=i;

vl(e[i].id);

if(st[e[i].id]<2)

puts("UNDEF");

else

printf("%d\n",v[e[i].id]);

}

else if(e[i].ins==3)

{

es=i+1;

}

int main()

{

init();

solve();

return 0;

}

在POJ上做过最冷门的题目了，算上我也才53个人AC。但貌似数据比较弱哦，总觉得比想象中要顺利得多……

果壳万有青年大烩杂记

1条回复

上周天跑去参加了下果壳三周年庆，挺有意思的，趁现在有时间了也稍微写写。

果壳网算是我平时最常刷的网站之一了，很多有意思的文章。这次得知他们在做三周年庆，却是在byr上看到有人发帖子在讨论。大概看了下活动，发现都挺有意思，心血来潮之下便约了克劳汀小姐陪我一起去玩。但由于各个子活动是要分别买票的，我又动作太慢，就只买到了iOS音乐坊、指哪儿打哪儿工作坊和万有青年烩之“场”的票。但就时间上来说，却是刚好没有冲突地分布在一天的各个时段，于是行程就确定啦。

跟克劳汀小姐见面是在10：30，离上一次约她出来玩已经过了快一年了呢……时间过得实在太快。音乐坊是11点开始，提前入场之后就闲聊了下。此时我才知道她下周竟然要去联合国实习了，在纽约待整整半年！虽然知道克劳汀小姐能力很强，平时也喜欢满世界跑，但能申请到联合国的实习，实在是让我吃惊不小（当然很好地藏在了我深邃平静的外表之下）。

很快主角们就入场了，带着一堆键盘音箱和ipad。总共是5人，其中“键盘哥”（也就是活动主讲人）应该是老大，是北京一所中学的音乐老师。开场调试了下设备，便为我们演奏了一曲加勒比海盗。效果实在是，大赞！！！（可惜没有拍下来……）随后键盘哥也跟我们简单介绍了下他们乐队（Sound Energy）的故事，又讲了讲ipad上创作电子音乐的一些软件。看起来很棒哦，但可惜我实在是对音乐一窍不通……现在的小朋友能有这样的音乐老师，实在是很幸福的事……

音乐会结束后，便跟克劳汀小姐简单吃了下午餐。由于时间上不允许走太远，就近找了间沙县小吃。吃饭的时候也听她讲了讲学校的事啦（老师如何如何push），律师行业的一些事情啦（原来律师和程序员一样，加班很严重，但相应薪水也不低）等等等等。相应的她也对IT行业不太熟悉呢，没有旁人在的情况下我也就毫无顾忌的一通乱吹（千万不要信我啊）……

午饭过后就回到了冈措咖啡继续参加活动。和之前不同的是，这次的指哪儿打哪儿需要切切实实动手参与了。（这次有拍照）

右上角是电烙铁，那个枪一样的东西是热熔枪，还有一堆镊子芯片导线云云的，动手能力一向不强的我只能强装镇定，不能在女生面前丢我们理科生的脸面啊。总而言之，这次的任务大概如此：芯片内含一个陀螺仪和加速器，需要为它加装一个音频接口，并刷一个开源的Arduino程序进去，这样该芯片便能将运动数据传输出来，进而可以实现对其他设备的控制……不过呢，克劳汀小姐完全没有在听的样子“那个人讲的东西我都听不懂哦，全靠你了”，但我也只是懵懵懂懂。又看到旁边几位仁兄理所当然般二话不说拿起电烙铁就开始各种操作，当时只能说是亚历山大……

无论如何，硬着头皮也是要上的。其实边看示意图，边问人，边有现场技术人员指导，操作起来也还不算太难……当时大概就是这个挫样：

说起来我好像也是第一次玩电烙铁，其实也不算难用哦，先预热到一定温度，然后把焊锡预先熔解或是边焊边添加在焊接位，稍微小心一点不要短路，就可以了。还有热熔胶枪，其实就是将一根胶棒加热后变成类似胶水样的熔胶，再滴在芯片上以粘合固定音频接口，就可以了~ 旁边的克劳汀小姐虽是文科生，也没有太多阻碍地进行着操作：

顺便提一下，这次活动的主持人于峰老师也是文科出身的（北大毕业），包括各种开源程序也玩得很溜的样子……实在是……不好意思说自己学的是计算机呢。

大概2个小时之后…………终于做出成品啦！！

随后便是把芯片交给老师，刷入Arduino程序。上一张老师酷酷的背影：

刷程序的时候还有点小插曲……由于很多人要刷程序，我便排队等在后面。但看着前面不少人都·失·败·了·。也就是刷程序进去后，无法读取运动数据。实在是很悲惨的事情，老师也无可奈何地说，可以再给你们一套材料，但可能要自己回去做了（时间不够）。终于轮到我了，双手颤抖地交出了我的两颗小芯片。随后悲剧发生了，插上线之后完全没有反应！两个都是！老师还调侃到“这两颗芯片恐怕出自一人之手吧”，我也只能一遍遍默念“注意保持微笑注意保持微笑”。但老师灵机一动地想到可能是USB线的问题。果然，换了另一条数据线后，两颗芯片都能正确工作了！

可以在屏幕中看到，下方的波浪线是读取到的芯片中陀螺仪记录到x、y、z三个方向的运动情况。实在是很开心……随后也看老师演示了如何用芯片控制摄像头：

以及四轴飞行器：

实在是让我大开眼界……尤其是了解到这些芯片设备等等其实一点也不贵……受限的更多是思想而不是物质条件呢……

晚餐是去了克劳汀小姐推荐的糖朝，没办法除了粤菜其他真的吃不太惯……点了牛肉肠、煎萝卜糕、扬州炒饭以及蒜蓉菜心，味道还算可以吧，但茶水有点小失望……（回木马剧场的路上看到了一台白色Ferrari 458 Italia新车…太美了）

晚上的万有青年烩之“场”也是这次果壳三周年活动的最后一幕，就嘉宾知名度来说，确实不如之前的“聚”和“力”，但听完之后还是觉得不少嘉宾很有意思（但很可惜我都没照/录相……），包括开场的二师兄乐队（一段他们以前活动的视频）、边周游世界边画画的Odding、来自台湾的剧作人小令等等等等……场内的音效则是中午才为我们表演过的“键盘哥”负责的，两个主持人加菲众和小姬也是各种逗趣……实在是太过开心的一晚，真的很久没有这样大声笑出来了。

期间也和克劳汀小姐闲聊了下，发现她的阅读量真的很大。我随口说出的书名、作者，她统统知道。包括最近读的毛姆、加缪，以及王小波、刘瑜、周濂等等。当我试探着问她，“你知道章诒和吗？她的《往事并不如烟》？”，得到回答“废话，这本书还有新版的《最后的贵族》呢”时，真的是发自内心的很开心……这种感觉，仿佛就是来到了另一颗星球，但却发现这颗星球的人竟然和你说同一种语言。

如果要说这次大烩有什么不足的话……大概就是不太守时了。包括各种活动的开始、结束时间基本都延后了……这次的“场”竟然拖到快22点才完。匆匆从会场出来之后，只能打车回去了。按照惯例，还是先送了克劳汀小姐回外交学院。期间路过的长安街，也还是一如既往的美。一年半前给我印象最深的这条街，大概也算是想留北京的一点动因了吧……

最后回到北邮已经22：40了，短信报过平安后也就洗涮休息了。

[POJ 3169]

发表回复

Layout

差分约束系统。

有n只牛，每只牛i对应x轴上一点di，对于i < j，有di <= dj。存在ml个关系di >= dj – k，其中i < j；又存在md个关系di <= dj - k，其中i < j。要求d[n] - d[1]最大值。若关系无法满足，输出-1；若最大值为无穷，输出-2。由于题目所求的是限制约束下的最大值，也即需要取大于等于号建立差分约束系统，那么3种边分别有： dj >= di
di + k >= dj
dj – k >= di

初始化除d1外的di值为无穷大，便可以用SPFA求解了。每次当 di + k < dj 时，进行松弛 dj = di + k。但是……用栈跑SPFA时却无限WA。换成队列一下就AC了。找到了原始数据后又看了别人的程序，最后发现问题出在了判负环上。基于队列的SPFA是用入栈次数>n来判断是否存在负环的，而姜碧野的《SPFA算法的优化与应用》中深搜的SPFA通过节点是否在栈中判负环是针对递归实现的。而我写的是基于栈的非递归SPFA，用的还是根据入栈次数>n判负环，但却发现很易出现误判。猜测由于深搜SPFA可以说是“盲目”推进的，也即有可能过多地沿回边更新，而导致入栈次数超过n，但实际却不存在负环。例如下图的例子：

最后的解是d[1..5] = {0, 4, 6, 10, 3}，其中结点5的入栈次数高达8次，但仍是无负环的。

在这题中，如果改变邻接表中边的顺序，让深搜SPFA尽量往图的深处推进，就能使用入栈次数来正确地判断负环了。可惜没有找到通用的严格证明……

#include<cstdio>
#include<cstring>

int n,ml,md,hd[1001],el,d[1001],b[1001],c[1001];
int stk[1000],sl;

struct E
{
    int v,d,p;
}e[100000];

inline void adde(int u,int v,int d)
{
    e[el].v=v; e[el].d=d; e[el].p=hd[u]; hd[u]=el++;
}

void init()
{
    int i,j,k,l;
    el=0;
    sl=0;
    memset(hd,-1,sizeof hd);
    memset(b,0,sizeof b);
    memset(c,0,sizeof c);
    for(i=1;i<=n;i++)
        d[i]=0x7fffffff;
    while(ml--)
    {
        scanf("%d%d%d",&i,&j,&k);
        adde(i,j,k);
    }
    while(md--)
    {
        scanf("%d%d%d",&i,&j,&k);
        adde(j,i,-k);
    }
    for(i=2;i<=n;i++)
        adde(i,i-1,0);
}

int solve()
{
    int i,j,k,l;
    b[1]=1;
    d[1]=0;
    stk[sl++]=1;
    while(sl)
    {
        i=stk[--sl];
        b[i]=0;
        for(l=hd[i];l!=-1;l=e[l].p)
        {
            j=e[l].v;
            k=e[l].d;
            if(d[i]+k<d[j])
            {
                d[j]=d[i]+k;
                if(!b[j])
                {
                    if(++c[j]>n)
                        return -1;
                    b[j]=1;
                    stk[sl++]=j;
                }
            }
        }
    }
    if(d[n]==0x7fffffff)
        return -2;
    return d[n]-d[1];
}

int main()
{
    int i,j;
    while(~scanf("%d%d%d",&n,&ml,&md))
    {
        init();
        printf("%d\n",solve());
    }
    return 0;
}

#include<cstdio>

#include<cstring>

int n,ml,md,hd[1001],el,d[1001],b[1001],c[1001];

int stk[1000],sl;

struct E

{

int v,d,p;

}e[100000];

inline void adde(int u,int v,int d)

{

e[el].v=v; e[el].d=d; e[el].p=hd[u]; hd[u]=el++;

}

void init()

{

int i,j,k,l;

el=0;

sl=0;

memset(hd,-1,sizeof hd);

memset(b,0,sizeof b);

memset(c,0,sizeof c);

for(i=1;i<=n;i++)

d[i]=0x7fffffff;

while(ml--)

{

scanf("%d%d%d",&i,&j,&k);

adde(i,j,k);

}

while(md--)

{

scanf("%d%d%d",&i,&j,&k);

adde(j,i,-k);

}

for(i=2;i<=n;i++)

adde(i,i-1,0);

}

int solve()

{

int i,j,k,l;

b[1]=1;

d[1]=0;

stk[sl++]=1;

while(sl)

{

i=stk[--sl];

b[i]=0;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].v;

k=e[l].d;

if(d[i]+k<d[j])

{

d[j]=d[i]+k;

if(!b[j])

{

if(++c[j]>n)

return -1;

b[j]=1;

stk[sl++]=j;

}

if(d[n]==0x7fffffff)

return -2;

return d[n]-d[1];

}

int main()

{

int i,j;

while(~scanf("%d%d%d",&n,&ml,&md))

{

init();

printf("%d\n",solve());

}

return 0;

}

结论就是：下次还是老老实实用队列判负环吧……

[POJ 2165]

发表回复

Gunman

计算几何。

题意是，在一个三维直角坐标系上，有平行于xOy平面的n个矩形，其边与x、y轴平行，坐标取值范围(0,1000)。问在x轴上是否存在一点能引出一条直线与所有矩形都相交。

这题读完后，并没有太直观的思路。但由于数据规模不大，考虑用三分法。每次对枚举的double m，按z值的增序遍历所有矩形，维护一个窗口作为能与所有矩形都相交的区域，最后返回相交矩形的数目。基本的想法是，由于矩形是连续且规则的图形，那么若解存在，则必定有最大值为n的单峰存在。但WA了数次后发现，由于返回值是离散的，就无法通过严格单调性来对三分法上下界进行修改了。

随后又发现，m值的所有可能取值其实是有限的，为某两个矩形i和j间(xi,0,zi)与(xj,0,zj)所确定的直线与x轴的交点，这里xi或xj可以是矩形的左或右边界。因此枚举的m值总数是O(n^2)的。而用前面描述的遍历方法便能确定从该点出发是否与所有矩形相交。所以总复杂度是O(n^3)的。在n=100的情况下，是可以AC的。最后跑了235ms。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define eps 1e-8

int n;
double x1[100],y1[100],x2[100],y2[100],z[100];

void init()
{
    int i;
    for(i=0;i<n;i++)
        scanf("%lf%lf%lf%lf%lf",x1+i,y1+i,x2+i,y2+i,z+i);
}

int calc(double m)
{
    int i,d;
    double xl,yb,xr,yt;
    for(xl=x1[0],yb=y1[0],xr=x2[0],yt=y2[0],i=1,d=1;i<n;i++)
    {
        xl=m+(xl-m)/z[i-1]*z[i]; yb=yb/z[i-1]*z[i];
        xr=m+(xr-m)/z[i-1]*z[i]; yt=yt/z[i-1]*z[i];
        xl=min(xr,max(xl,x1[i]));
        yb=min(yt,max(yb,y1[i]));
        xr=max(xl,min(xr,x2[i]));
        yt=max(yb,min(yt,y2[i]));
        if(xl>x1[i]-eps&&xl<x2[i]+eps
                &&yb>y1[i]-eps&&yb<y2[i]+eps)
            d++;
    }
    return d;
}

void mksol(double m)
{
    int i;
    double xl,yb,xr,yt;
    puts("SOLUTION");
    printf("%.6f\n",m);
    for(xl=x1[0],yb=y1[0],xr=x2[0],yt=y2[0],i=1;i<n;i++)
    {
        xl=m+(xl-m)/z[i-1]*z[i]; yb=yb/z[i-1]*z[i];
        xr=m+(xr-m)/z[i-1]*z[i]; yt=yt/z[i-1]*z[i];
        xl=min(xr,max(xl,x1[i]));
        yb=min(yt,max(yb,y1[i]));
        xr=max(xl,min(xr,x2[i]));
        yt=max(yb,min(yt,y2[i]));
    }
    for(i=0;i<n;i++)
        printf("%.6f %.6f %.6f\n",m+(xl-m)/z[n-1]*z[i],
                yb/z[n-1]*z[i],z[i]);
}

void solve()
{
    int i,j;
    double m;
    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            m=x1[i]-z[i]*(x1[i]-x2[j])/(z[i]-z[j]);
            if(calc(m)==n)
                break;
            m=x1[i]-z[i]*(x1[i]-x1[j])/(z[i]-z[j]);
            if(calc(m)==n)
                break;
            m=x2[i]-z[i]*(x2[i]-x1[j])/(z[i]-z[j]);
            if(calc(m)==n)
                break;
            m=x2[i]-z[i]*(x2[i]-x2[j])/(z[i]-z[j]);
            if(calc(m)==n)
                break;
        }
        if(j<n)
            break;
    }
    if(i==n-1)
        puts("UNSOLVABLE");
    else
        mksol(m);
}

int main()
{
    while(~scanf("%d",&n))
    {
        init();
        solve();
    }
    return 0;
}

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define eps 1e-8

int n;

double x1[100],y1[100],x2[100],y2[100],z[100];

void init()

{

int i;

for(i=0;i<n;i++)

scanf("%lf%lf%lf%lf%lf",x1+i,y1+i,x2+i,y2+i,z+i);

}

int calc(double m)

{

int i,d;

double xl,yb,xr,yt;

for(xl=x1[0],yb=y1[0],xr=x2[0],yt=y2[0],i=1,d=1;i<n;i++)

{

xl=m+(xl-m)/z[i-1]*z[i]; yb=yb/z[i-1]*z[i];

xr=m+(xr-m)/z[i-1]*z[i]; yt=yt/z[i-1]*z[i];

xl=min(xr,max(xl,x1[i]));

yb=min(yt,max(yb,y1[i]));

xr=max(xl,min(xr,x2[i]));

yt=max(yb,min(yt,y2[i]));

if(xl>x1[i]-eps&&xl<x2[i]+eps

&&yb>y1[i]-eps&&yb<y2[i]+eps)

d++;

}

return d;

}

void mksol(double m)

{

int i;

double xl,yb,xr,yt;

puts("SOLUTION");

printf("%.6f\n",m);

for(xl=x1[0],yb=y1[0],xr=x2[0],yt=y2[0],i=1;i<n;i++)

{

xl=m+(xl-m)/z[i-1]*z[i]; yb=yb/z[i-1]*z[i];

xr=m+(xr-m)/z[i-1]*z[i]; yt=yt/z[i-1]*z[i];

xl=min(xr,max(xl,x1[i]));

yb=min(yt,max(yb,y1[i]));

xr=max(xl,min(xr,x2[i]));

yt=max(yb,min(yt,y2[i]));

}

for(i=0;i<n;i++)

printf("%.6f %.6f %.6f\n",m+(xl-m)/z[n-1]*z[i],

yb/z[n-1]*z[i],z[i]);

}

void solve()

{

int i,j;

double m;

for(i=0;i<n-1;i++)

{

for(j=i+1;j<n;j++)

{

m=x1[i]-z[i]*(x1[i]-x2[j])/(z[i]-z[j]);

if(calc(m)==n)

break;

m=x1[i]-z[i]*(x1[i]-x1[j])/(z[i]-z[j]);

if(calc(m)==n)

break;

m=x2[i]-z[i]*(x2[i]-x1[j])/(z[i]-z[j]);

if(calc(m)==n)

break;

m=x2[i]-z[i]*(x2[i]-x2[j])/(z[i]-z[j]);

if(calc(m)==n)

break;

}

if(j<n)

break;

}

if(i==n-1)

puts("UNSOLVABLE");

else

mksol(m);

}

int main()

{

while(~scanf("%d",&n))

{

init();

solve();

}

return 0;

}

[POJ 2043]

发表回复

Area of Polygons

计算几何。

题意是，给出一个多边形的顶点（坐标都为整数）描述，要求该多边形在网格上覆盖的格子数目。

基本思路是扫描线，从左到右，同时维护一个有序数组s，记录当前区间内存在的线段的y值，线段必定是成对出现的，且每对线段间的区域为多边形内部。这样就可以计算每个区间内被覆盖的格子数了。

具体的实现上，首先初始化所有的n条线段，并放入一个表头大小为4001的邻接表中，方便扫描线时将新扫到的线段加入。垂直的线段直接忽略。对线段结构体记录其当前y值，斜率k，终点xr，以及删除标记b。每次处理一个区间的线段时，删除线段即为将标记位置1。对s内的线段排序时，首先将被删除的线段都放到最后，然后若y值不同则按y从小到大排序，否则再按斜率k从小到大排序。

计算每段区间[x,x+1]内被覆盖的格子数时，需要注意若连续的多条线段过于接近，要避免重复计算。同时取floor或ceil时，需要对y值增或减eps，以舍去计算误差。

总体上来说虽然细节较多，仔细思考后还是比较顺利地1A了。不过也写了一整个下午……

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

#define eps 1e-8

int n,hd[4001],el,ans,sl;
int x[100],y[100],mnx,mxx;

struct E
{
    double y,k;
    int b,xr,p;
}e[100],s[100];

struct CP
{
    bool operator () (const E &p,const E &q) const
    {
        if(p.b>q.b) return 0;
        if(p.b<q.b) return 1;
        if(abs(p.y-q.y)>eps)
            return p.y<q.y;
        else
            return p.k<q.k;
    }
};

inline void adde(int x0,int y0,int x1,int y1)
{
    if(x0==x1) return;
    if(x0>x1)
    {
        x0^=x1^=x0^=x1;
        y0^=y1^=y0^=y1;
    }
    e[el].y=y0;
    e[el].k=1.0*(y1-y0)/(x1-x0);
    e[el].b=0;
    e[el].xr=x1;
    e[el].p=hd[x0];
    hd[x0]=el++;
}

void init()
{
    int i,j,k,l;
    el=sl=ans=0;
    mnx=4001;
    mxx=0;
    memset(hd,-1,sizeof hd);
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        x[i]+=2000;
        y[i]+=2000;
        mxx=max(mxx,x[i]);
        mnx=min(mnx,x[i]);
    }
    adde(x[n-1],y[n-1],x[0],y[0]);
    for(i=0;i<n-1;i++)
        adde(x[i],y[i],x[i+1],y[i+1]);
}

void solve()
{
    int i,j,k,l;
    double yb,yt;
    E *p,*q;
    for(i=mnx;i<mxx;i++)
    {
        k=ans;
        for(l=0;l<sl&&!s[l].b;l++)
        {
            if(s[l].xr==i)
                s[l].b=1;
        }
        for(l=hd[i];l!=-1;l=e[l].p)
            s[sl++]=e[l];
        sort(s,s+sl,CP());
        if(s[0].b)
            continue;
        yt=-1e30;
        for(l=0;l<sl&&!s[l].b;l+=2)
        {
            p=&s[l];
            q=&s[l+1];
            yb=min(floor(p->y+eps),floor(p->y+p->k+eps));
            if(yb<yt)
                yb=yt;
            yt=max(ceil(q->y-eps),ceil(q->y+q->k-eps));
            p->y+=p->k;
            q->y+=q->k;
            ans+=yt-yb;
        }
    }
    printf("%d\n",ans);
}

int main()
{
    while(~scanf("%d",&n)&&n)
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define eps 1e-8

int n,hd[4001],el,ans,sl;

int x[100],y[100],mnx,mxx;

struct E

{

double y,k;

int b,xr,p;

}e[100],s[100];

struct CP

{

bool operator () (const E &p,const E &q) const

{

if(p.b>q.b) return 0;

if(p.b<q.b) return 1;

if(abs(p.y-q.y)>eps)

return p.y<q.y;

else

return p.k<q.k;

}

};

inline void adde(int x0,int y0,int x1,int y1)

{

if(x0==x1) return;

if(x0>x1)

{

x0^=x1^=x0^=x1;

y0^=y1^=y0^=y1;

}

e[el].y=y0;

e[el].k=1.0*(y1-y0)/(x1-x0);

e[el].b=0;

e[el].xr=x1;

e[el].p=hd[x0];

hd[x0]=el++;

}

void init()

{

int i,j,k,l;

el=sl=ans=0;

mnx=4001;

mxx=0;

memset(hd,-1,sizeof hd);

for(i=0;i<n;i++)

{

scanf("%d%d",&x[i],&y[i]);

x[i]+=2000;

y[i]+=2000;

mxx=max(mxx,x[i]);

mnx=min(mnx,x[i]);

}

adde(x[n-1],y[n-1],x[0],y[0]);

for(i=0;i<n-1;i++)

adde(x[i],y[i],x[i+1],y[i+1]);

}

void solve()

{

int i,j,k,l;

double yb,yt;

E *p,*q;

for(i=mnx;i<mxx;i++)

{

k=ans;

for(l=0;l<sl&&!s[l].b;l++)

{

if(s[l].xr==i)

s[l].b=1;

}

for(l=hd[i];l!=-1;l=e[l].p)

s[sl++]=e[l];

sort(s,s+sl,CP());

if(s[0].b)

continue;

yt=-1e30;

for(l=0;l<sl&&!s[l].b;l+=2)

{

p=&s[l];

q=&s[l+1];

yb=min(floor(p->y+eps),floor(p->y+p->k+eps));

if(yb<yt)

yb=yt;

yt=max(ceil(q->y-eps),ceil(q->y+q->k-eps));

p->y+=p->k;

q->y+=q->k;

ans+=yt-yb;

}

printf("%d\n",ans);

}

int main()

{

while(~scanf("%d",&n)&&n)

{

init();

solve();

}

return 0;

}

[POJ 3130]

发表回复

How I Mathematician Wonder What You Are!

判断多边形内核。

题意为N个顶点逆时针顺序描述的一个多边形，要求判断该多边形是否有“内核”。所谓“内核”，就是在该多边形内的一块区域，站在这块区域内任意一点观察多边形的内部，都可以无死角地看遍整个多边形。

解这题涉及到半平面的概念。其实就是每条线段都会将平面区域划分成两部分，一部分包含多边形内部，一部分不包含。那么，将所有线段对应的包含多边形内部那一半的平面区域求交集，就得到了多边形的内核（如果存在）或者空集（不存在内核）。

进一步考虑实现问题的话，可以将每条直线描述为ax+by+c=0，那么半平面方程即为ax+by+c>=0，其中a、b、c三个系数，根据直线的朝向以及题目给定的逆时针顺序，a是取-1或1的，进而可以确定b和c。多边形的内核区域，可以抽象为某些点，进一步分析可以发现，若存在内核，则其角一定是某两条边所在直线的交点。由于最多只有50条边，那么可以枚举n(n-1)/2个交点，依次代入n个半平面方程，看是否存在点满足对所有半平面方程都大于0即可。

#include<cstdio>
#include<cstring>
#include<list>
using namespace std;

#define eps 1e-8

int n,el,ll,hd;
double x[50],y[50];

struct L
{
    double a,b,c;
}l[50];

struct E
{
    double x,y;
    E(double a,double b): x(a),y(b) {};
};

list<E>L;

inline double abs(double a)
{
    return a>0?a:-a;
}

inline void addl(double x1,double y1,double x2,double y2)
{
    double xd,yd,a,b,c;
    if(abs(xd=x2-x1)<eps)
    {
        if(y2<y1)
        {
            a=1;
            c=-x1;
        }
        else
        {
            a=-1;
            c=x1;
        }
        b=0;
    }
    else if(abs(yd=y2-y1)<eps)
    {
        a=0;
        if(x2>x1)
        {
            b=1;
            c=-y1;
        }
        else
        {
            b=-1;
            c=y1;
        }
    }
    else
    {
        a=1;
        b=(x2-x1)/(y1-y2);
        c=-x1-b*y1;
        if(yd>0)
        {
            a=-a; b=-b; c=-c;
        }
    }
    l[ll].a=a; l[ll].b=b; l[ll].c=c; ll++;
}

inline void adde(int i,int j)
{
    double a1=l[i].a,b1=l[i].b,c1=l[i].c;
    double a2=l[j].a,b2=l[j].b,c2=l[j].c;
    if(abs(a1)<eps&&abs(a2)<eps||abs(b1)<eps&&abs(b2)<eps)
        return;
    if(abs(a1/b1-a2/b2)<eps)
        return;
    double x,y;
    if(abs(a1)<eps)
    {
        y=-c1/b1;
        x=-(b2*y+c2)/a2;
    }
    else if(abs(b1)<eps)
    {
        x=-c1/a1;
        y=-(c2+a2*x)/b2;
    }
    else
    {
        y=(a2/a1*c1-c2)/(b2-a2/a1*b1);
        x=-(b1*y+c1)/a1;
    }
    L.push_back(E(x,y));
}

void init()
{
    int i,j,k;
    L.clear();
    hd=-1;
    el=ll=0;
    for(i=0;i<n;i++)
        scanf("%lf%lf",&x[i],&y[i]);
    for(i=0;i<n-1;i++)
        addl(x[i],y[i],x[i+1],y[i+1]);
    addl(x[n-1],y[n-1],x[0],y[0]);
    for(i=0;i<n-1;i++)
        for(j=i+1;j<n;j++)
            adde(i,j);
}

void solve()
{
    int i,j,k;
    double a,b,c,x,y;
    list<E>::iterator lit;
    for(i=0;i<ll;i++)
    {
        a=l[i].a; b=l[i].b; c=l[i].c;
        for(lit=L.begin();lit!=L.end();)
        {
            x=lit->x; y=lit->y;
            if(a*x+b*y+c<-eps)
                L.erase(lit++);
            else
                lit++;
        }
    }
    if(L.size())
        puts("1");
    else
        puts("0");
}

int main()
{
    while(~scanf("%d",&n)&&n)
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

#include<cstdio>

#include<cstring>

#include<list>

using namespace std;

#define eps 1e-8

int n,el,ll,hd;

double x[50],y[50];

struct L

{

double a,b,c;

}l[50];

struct E

{

double x,y;

E(double a,double b): x(a),y(b) {};

};

list<E>L;

inline double abs(double a)

{

return a>0?a:-a;

}

inline void addl(double x1,double y1,double x2,double y2)

{

double xd,yd,a,b,c;

if(abs(xd=x2-x1)<eps)

{

if(y2<y1)

{

a=1;

c=-x1;

}

else

{

a=-1;

c=x1;

}

b=0;

}

else if(abs(yd=y2-y1)<eps)

{

a=0;

if(x2>x1)

{

b=1;

c=-y1;

}

else

{

b=-1;

c=y1;

}

else

{

a=1;

b=(x2-x1)/(y1-y2);

c=-x1-b*y1;

if(yd>0)

{

a=-a; b=-b; c=-c;

}

l[ll].a=a; l[ll].b=b; l[ll].c=c; ll++;

}

inline void adde(int i,int j)

{

double a1=l[i].a,b1=l[i].b,c1=l[i].c;

double a2=l[j].a,b2=l[j].b,c2=l[j].c;

if(abs(a1)<eps&&abs(a2)<eps||abs(b1)<eps&&abs(b2)<eps)

return;

if(abs(a1/b1-a2/b2)<eps)

return;

double x,y;

if(abs(a1)<eps)

{

y=-c1/b1;

x=-(b2*y+c2)/a2;

}

else if(abs(b1)<eps)

{

x=-c1/a1;

y=-(c2+a2*x)/b2;

}

else

{

y=(a2/a1*c1-c2)/(b2-a2/a1*b1);

x=-(b1*y+c1)/a1;

}

L.push_back(E(x,y));

}

void init()

{

int i,j,k;

L.clear();

hd=-1;

el=ll=0;

for(i=0;i<n;i++)

scanf("%lf%lf",&x[i],&y[i]);

for(i=0;i<n-1;i++)

addl(x[i],y[i],x[i+1],y[i+1]);

addl(x[n-1],y[n-1],x[0],y[0]);

for(i=0;i<n-1;i++)

for(j=i+1;j<n;j++)

adde(i,j);

}

void solve()

{

int i,j,k;

double a,b,c,x,y;

list<E>::iterator lit;

for(i=0;i<ll;i++)

{

a=l[i].a; b=l[i].b; c=l[i].c;

for(lit=L.begin();lit!=L.end();)

{

x=lit->x; y=lit->y;

if(a*x+b*y+c<-eps)

L.erase(lit++);

else

lit++;

}

if(L.size())

puts("1");

else

puts("0");

}

int main()

{

while(~scanf("%d",&n)&&n)

{

init();

solve();

}

return 0;

}

最近都在练习计算几何的题目。感觉这类题有个特点是比较偏数学公式的推导，对复杂度的要求不会太高。

借这个机会好好复习下各种几何工具吧。

[POJ 3004]

发表回复

Subway planning

计算几何。

题意是，在二维平面上有n个点（不为原点且不重复），和距离值d，问最少从原点引出多少点射线，可以使得n个点离某条射线的最远距离都不超过d。

这题读完之后……基本是没有任何思路的。稍微分析一下可以发现，射线肯定都是刚好离某个点距离为d的。因此写了一个搜索，对任意一点，若未被覆盖，则（1）顺时侧置射线、（2）逆时侧置射线、（3）不置射线。结果TLE。又想了一些剪枝后，还是妥妥的TLE……

然后发现discuss基本是空的……就又google了一下题解，也去下载了题目的原始数据，花了整整一天时间，总算弄明白了。大致思路如下：

首先转换到极坐标系，并将每个点对应能被覆盖的射线位置范围视作区间，那么就可以将问题转化成区间覆盖问题：由于每个区间都是必定要被覆盖的，可以将区间按起始位置排序后，贪心地选择能按顺序地覆盖最多区间的位置放置射线，这可以通过取当前按序覆盖的区间中最左的右边界值来得到。每次下一个顺序区间无法被覆盖（左边界超过当前射线位置）时，贪心地重置射线位置为该区间的右边界值。所有n个区间处理完后便是最小覆盖射线数。

但这里有一个问题就是，极坐标是一个环形结构，无法确定哪个区间最为最左区间。考虑到这里n<=500，即使枚举每个区间为起始区间，算上排序，复杂度也只是O(n^2lgn)，是完全可以接受的。当然这里极坐标的计算形式以及弧度的处理还是有一些技巧的，比如atan2(y,x)函数直接根据y和x值返回取值范围在(-PI,PI]范围的弧度值，另外标程还用到了一个fmod(a,b)函数，是对浮点数算a - b*k = c，abs(c)

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define PI 3.1415926535897932384626
#define eps 1e-8

int n,ans;
double d;

struct E
{
    double b,e;
    bool operator < (const E &p) const
    {
        return b<p.b;
    }
}e[1000],ee[1000];

void init()
{
    int i,j;
    double x,y,a,r,am;
    ans=0x7fffffff;
    for(i=j=0;i<n;i++)
    {
        scanf("%lf%lf",&x,&y);
        a=atan2(y,x);
        r=sqrt(y*y+x*x);
        if(r<d+eps)
            continue;
        am=asin(d/r);
        e[j].b=a-am;
        e[j].e=a+am;
        j++;
    }
    n=j;
    sort(e,e+n);
}

int calc(int i)
{
    int j,k,l;
    double top;
    for(j=i;j<n;j++)
    {
        ee[j-i].b=e[j].b;
        ee[j-i].e=e[j].e;
    }
    for(j=0;j<i;j++)
    {
        ee[n-i+j].b=e[j].b+2*PI;
        ee[n-i+j].e=e[j].e+2*PI;
    }
    for(i=l=1,top=ee[0].e;i<n;i++)
    {
        if(top<ee[i].b-eps)
        {
            l++;
            top=ee[i].e;
        }
        else if(top>ee[i].e+eps)
            top=ee[i].e;
    }
    return l;
}

void solve()
{
    int i;
    for(i=0;i<n;i++)
        ans=min(ans,calc(i));
    if(ans==0x7fffffff)
        ans=0;
    printf("%d\n",ans);
}

int main()
{
    scanf("%*d");
    while(~scanf("%d%lf",&n,&d))
    {
        init();
        solve();
    }
    return 0;
}

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define PI 3.1415926535897932384626

#define eps 1e-8

int n,ans;

double d;

struct E

{

double b,e;

bool operator < (const E &p) const

{

return b<p.b;

}

}e[1000],ee[1000];

void init()

{

int i,j;

double x,y,a,r,am;

ans=0x7fffffff;

for(i=j=0;i<n;i++)

{

scanf("%lf%lf",&x,&y);

a=atan2(y,x);

r=sqrt(y*y+x*x);

if(r<d+eps)

continue;

am=asin(d/r);

e[j].b=a-am;

e[j].e=a+am;

j++;

}

n=j;

sort(e,e+n);

}

int calc(int i)

{

int j,k,l;

double top;

for(j=i;j<n;j++)

{

ee[j-i].b=e[j].b;

ee[j-i].e=e[j].e;

}

for(j=0;j<i;j++)

{

ee[n-i+j].b=e[j].b+2*PI;

ee[n-i+j].e=e[j].e+2*PI;

}

for(i=l=1,top=ee[0].e;i<n;i++)

{

if(top<ee[i].b-eps)

{

l++;

top=ee[i].e;

}

else if(top>ee[i].e+eps)

top=ee[i].e;

}

return l;

}

void solve()

{

int i;

for(i=0;i<n;i++)

ans=min(ans,calc(i));

if(ans==0x7fffffff)

ans=0;

printf("%d\n",ans);

}

int main()

{

scanf("%*d");

while(~scanf("%d%lf",&n,&d))

{

init();

solve();

}

return 0;

}

ps: 今天老师说可以公费买一些书（归实验室但实际是给我们看），京东也很合时宜地给了我几张优惠劵……结果便一发不可收拾了……稍微列下书单：语言类： Ruby元编程
 Python核心编程
 Python Cookbook
K&R
Erlang/OTP并发编程实战
 Node.js开发指南
 JavaScript语言精髓与编程实践

算法类：
TAOCP卷1
TAOCP卷2
TAOCP卷3
CLRS

IT文化类：
谁说大象不能跳舞？
代码的未来
 浪潮之巅
 图灵的秘密：他的生平、思想及论文解读

其他：
HTTP权威指南

其中有些是看过但出了新版的，比如CLRS、浪潮之巅；有些是可以有计划地读完的，如IT文化类的其他几本；有些是参考书，如语言类和其他；有些是纯粹是买来拜的……我不说你也知道是哪些……