[POJ 3004] | Eurce's Blog

计算几何。

题意是，在二维平面上有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文化类的其他几本；有些是参考书，如语言类和其他；有些是纯粹是买来拜的……我不说你也知道是哪些……