题解：P10876 [COTS/CETS 2022] 点组 Točkice

100Accepted · 2024-08-27 12:54:37 · 题解

特判 n \le 2。

先计算凸包上的点的个数，其最后可以连成 n+(n-3) 条线段（以一个点向周围所有凸包上的点连线有 n-3 条）。其次求凸包内点的个数。凸包内的每一个点都可以向所在的以上面方法求得的三角形的三个顶点连线。

按三角剖分，设凸包上有 m 个点，按上述方法计算，共有 m+(m-3)+3(n-m) 条线段，最佳情况奇偶性不变（证明太难，不放），奇数 Alenka 胜，偶数 Bara 胜。

Code：（代码其实不用判三点一线的情况）

#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int n,ans=0,cnt=1;
double tmp,mid;
struct ld{
    double x,y;
}p[100005],s[100005];
double ok(ld a1,ld a2,ld b1,ld b2){
    return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);
}
double jl(ld p1,ld p2){
    return sqrt((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));
}
bool cmp(ld p1,ld p2){
    if(p1.x==p2.x&&p2.x==p[1].x){
        if(p1.y>p2.y)return 0;
        return 1;
    }
    if(p1.x!=p[1].x&&p2.x!=p[1].x)
    if((p1.y-p[1].y)/(p1.x-p[1].x)==(p2.y-p[1].y)/(p2.x-p[1].x)){
        if(abs(p2.x-p[1].x)>abs(p1.x-p[1].x))return 1;
        return 0;
    }
    tmp=ok(p[1],p1,p[1],p2);
    if(tmp>0)return 1;
    if(tmp==0&&jl(p[0],p1)<jl(p[0],p2))return 1;
    return 0;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lf%lf",&p[i].x,&p[i].y);
        if(i!=1&&(p[i].y<p[1].y||(p[i].y==p[1].y&&p[i].x<p[1].x))){
            mid=p[1].y;p[1].y=p[i].y;p[i].y=mid;
            mid=p[1].x;p[1].x=p[i].x;p[i].x=mid;
        }
    }
    if(n==1){
        printf("Bara");
        return 0;
    }
    if(n==2){
        printf("Alenka");
        return 0;
    }
    sort(p+2,p+1+n,cmp);
    s[1]=p[1];
    for(int i=2;i<=n;i++){
        while(cnt>1&&ok(s[cnt-1],s[cnt],s[cnt],p[i])<=0)cnt--;
        cnt++;
        s[cnt]=p[i];
    }
    s[cnt+1]=p[1];
    ans=cnt+cnt-3+3*(n-cnt);
    if(ans&1)printf("Alenka");
    else printf("Bara");
    return 0;
}