[关闭]
@Jerusalem 2016-02-14T12:15:33.000000Z 字数 1534 阅读 1119

Vol5


JSOI2010 Group
BZOJ1821

显然,我们可以二分最大的最小值,记为ans。

如果两个点之间的距离小于这个ans,也就是说这两个点必须被划进一个部落,则我们将这两个点置于一个集合中。

我们证明:在ans意义下,问题有解的充分必要条件是非空集合的数量大于等于k个。

必要性是显然的,下证充分性。

显然,这k个集合划分为k个部落,每个部落之间都不会有距离小于ans的点对(否则将置于同一个集合)

如果集合数大于k,我们将大于k的部分作为一个部落,显然之间也没有距离小于ans的点对,与其它集合也没有。Q.E.D

维护集合,我们可以使用并查集。

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <iostream>
  7. using namespace std;
  8. const int maxn=1005;
  9. struct UnionFind{
  10. int fa[maxn];
  11. UnionFind(){
  12. for(int i=0;i<maxn;i++)
  13. fa[i]=i;
  14. }
  15. void Clear(){
  16. for(int i=0;i<maxn;i++)
  17. fa[i]=i;
  18. }
  19. int find(int a){
  20. if(fa[a]!=a)
  21. fa[a]=find(fa[a]);
  22. return fa[a];
  23. }
  24. bool Near(int a,int b){
  25. return find(a)==find(b);
  26. }
  27. void Union(int a,int b){
  28. fa[find(a)]=find(b);
  29. }
  30. };
  31. struct Point{
  32. double x,y;
  33. Point(){
  34. x=0;
  35. y=0;
  36. }
  37. Point(double x_,double y_){
  38. x=x_;
  39. y=y_;
  40. }
  41. };
  42. Point People[maxn];
  43. bool used[maxn];
  44. UnionFind Tribal;
  45. int n,k;
  46. double Dis(Point a,Point b);
  47. bool CanDivide(double Distance)
  48. {
  49. Tribal.Clear();
  50. memset(used,false,sizeof(used));
  51. for(int i=1;i<=n;i++)
  52. for(int j=1;j<=n;j++)
  53. if(Dis(People[i],People[j])<Distance)
  54. Tribal.Union(i,j);
  55. for(int i=1;i<=n;i++)
  56. used[Tribal.find(i)]=true;
  57. int num=0;
  58. for(int i=1;i<=n;i++)
  59. if(used[i])
  60. num++;
  61. return num>=k;
  62. }
  63. void Solve()
  64. {
  65. double l=0,r=0x3f3f3f3f;
  66. while((r-l)>1e-4){
  67. double mid=(l+r)/2;
  68. if(CanDivide(mid+1e-5))
  69. l=mid+1e-5;
  70. else
  71. r=mid;
  72. }
  73. printf("%.2lf",l);
  74. }
  75. void Readdata()
  76. {
  77. freopen("loli.in","r",stdin);
  78. scanf("%d%d",&n,&k);
  79. for(int i=1;i<=n;i++){
  80. double x,y;
  81. cin>>x>>y;
  82. People[i]=Point(x,y);
  83. }
  84. }
  85. void Close()
  86. {
  87. fclose(stdin);
  88. fclose(stdout);
  89. }
  90. int main()
  91. {
  92. Readdata();
  93. Solve();
  94. Close();
  95. return 0;
  96. }
  97. double Dis(Point a,Point b)
  98. {
  99. return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
  100. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注