2020牛客暑假多校训练营（第二场）补题B，C

B Boundary

题目大意
给定n个点坐标，以(0,0)为起始点画圆，问最多能有多少个点在圆上。
解题思路
官方题解

看了题解之后，还是能明白这种做法的，但是利用这种方式解决可能有点难想。其实还有其它方法。
点O为(0,0)，由三点共圆，可以枚举点A，以OA为固定的弦，再找点B，OA与OB中垂线交点为必定经过点A,点B,点O的圆的圆心。因此我们找到所有圆心，看相同圆心有多少个，更新答案(最大值)，最后输出答案+1。时间复杂度是O(n^2)的。
注：记录相同圆心个数可以使用map。另外，为什么要在最外层循环，清空map，因为如果下一次循环，有与之前相同的圆心，其实在之前一次循环就会产生了，因此不清空的话会重复计算，而且这里的意思是以OA为固定的弦，看能有多少相同的圆心。

以这张图为例，以OA为弦的时候，加上了OB，OC，OD。如果不清空map，以OB，OC，OD为弦时，又会重复计算。
AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
const double eps=1e-5;
int n,ans;
typedef pair<double,double> pdd;
map<pdd,int>mp;
pdd p[maxn];
pdd circle_center(double x1,double y1,double x2,double y2,double x3,double y3)//三点共圆模板
{
    double a=x1-x2;
    double b=y1-y2;
    double c=x1-x3;
    double d=y1-y3;
    double e=((x1*x1-x2*x2)+(y1*y1-y2*y2))/2.0;
    double f=((x1*x1-x3*x3)+(y1*y1-y3*y3))/2.0;
    double det=b*c-a*d;
    if(det<eps&&det>(-eps))//三点共线
    return pdd{0,0};
    double x=-(d*e-b*f)/det;
    double y=-(a*f-c*e)/det;
    return pdd{x,y};//满足条件返回圆心
}
int main()
{
    scanf("%d",&n);
    //p[0]=make_pair(0,0);
    for(int i=1;i<=n;i++)
    {
        double x,y;
        scanf("%lf %lf",&x,&y);
        p[i]=make_pair(x,y);
    }
    for(int i=1;i<=n;i++)
    {
        mp.clear();
        for(int j=1;j<=n;j++)
        {
            if(i==j)
            continue;
            double x1=p[i].first,y1=p[i].second,x2=p[j].first,y2=p[j].second,x3=0,y3=0;
            pdd tmp=circle_center(x1,y1,x2,y2,x3,x3);
            if(tmp!=pdd{0,0})
            ans=max(ans,++mp[tmp]);
        }
    }
    printf("%d\n",ans+1);
    return 0;
}

C Cover the tree

题目大意
给定一个有n个点的无根树(即以任意点为根都可以)，问至少有多少条链，可以去覆盖整棵树的所有边。输出最少链个数。
解题思路
官方题解

官方题解解释的还是很详细的，这里再简要说明一下。
有n个点，首先，题目答案的下界为 叶子节点数/2(向上取整)，因为叶子节点有一条单独的边，除非从一个叶子节点到另一个叶子节点组成一条链，才能覆盖所有叶子节点的边。然后，我们就要证明答案的上界也是 叶子节点数/2(向上取整)。
第一，n=1,n=2,是需要特判一下的，因为之后要找的是以至少有两个儿子的节点为根来进行证明的。
第二，n>2且叶子节点为偶数，主要说明一下为什么这条边会被覆盖。

• R<=s/2，因为R是dfs序最后的叶子节点了，因此大于他的叶子节点，肯定不是在这条边为根节点的子树上，要通过这条边延伸出去，所以这条边必会被覆盖。
• L>s/2，因为L是dfs序最开始的叶子节点，因此小于他的叶子节点，肯定也不是在这条边为根节点的子树上，要通过这条边延伸出去，所以这条边必会被覆盖。
• R>s/2 L<=s/2，首先因为根节点至少有两个(这就是为什么要特判n=1,n=2)，所以每条边的叶子范围要不 L>1，要不R<n。如果L≠1，那么这条边也必须得延伸出去才能到 I₁，所以肯定经过。如果R≠n，那么这条边也必须延伸出去才能到 I_n。

第三，n>2且叶子节点数为奇数，只要在根添一个儿子节点，那么叶子节点数就变成偶数了，而且把根当作抽象的新的儿子效果是一样的，因此我们添一个儿子节点为根节点。
AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
struct node
{
    int to,next;
}edge[maxn<<1];
int head[maxn];
int ing[maxn];
vector<int>ans;
int cnt,root,n;
void add(int x,int y)
{
    edge[++cnt].to=y;
    edge[cnt].next=head[x];
    head[x]=cnt;
}
void dfs(int u,int fa)
{
    if(ing[u]==1)
    {
        ans.push_back(u);
        return ;
    }
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa)
        continue;
        dfs(v,u);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        ing[u]++;
        ing[v]++;
        add(u,v);
        add(v,u);
    }
    if(n==1)
    {
        puts("0");
        return 0;
    }
    if(n==2)
    {
        puts("1");
        puts("1 2");
        return 0;
    }
    for(int i=1;i<=n;i++)
    if(ing[i]>1)
    {
        root=i;
        break;
    }
    dfs(root,0);
    if(ans.size()%2==1)
    ans.push_back(root);
    printf("%d\n",ans.size()>>1);
    for(int i=1;i<=(ans.size()>>1);i++)
    {
        printf("%d %d\n",ans[i-1],ans[i+(ans.size()>>1)-1]);
    }
    return 0;
}