C++(g++ 7.5.0) 解法, 执行用时: 2020ms, 内存消耗: 744K, 提交时间: 2022-09-11 12:50:06

#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;

typedef long long LL;
const int N=60;
const double eps = 1e-11;
const double pi = acos(-1);

int dcmp(double x, double y){
    if(fabs(x - y) < eps) return 0;
    if(x < y) return -1;
    return 1;
}
int sign(double x){
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    return 1;
}

struct point{
    double x, y;
    int id;
    bool operator == (const point a) const {
        return !dcmp(x, a.x) && !dcmp(y, a.y);
    }
};
point operator + (point a, point b) { return {a.x + b.x, a.y + b.y}; }
point operator - (point a, point b) { return {a.x - b.x, a.y - b.y}; }
point operator * (point a, double b) { return {a.x * b, a.y * b}; }
point operator / (point a, double b) { return {a.x / b, a.y / b}; }

double cross(point a, point b) { return a.x * b.y - a.y * b.x; }
double dot(point a, point b) { return a.x * b.x + a.y * b.y; }
double angle(point a) { return atan2(a.y, a.x); }
point rotate(point a, double rad) { return {a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad)}; }


point P[N];
point tmp[N];
double divi[N * N * 4];
int cnt;
double ans[N][N];


void add(point v)
{
    if(v.x < 0) v.x = -v.x, v.y = -v.y;
    divi[cnt++] = pi / 2 - angle(v);
    divi[cnt] = divi[cnt - 1] + pi, cnt++; // 原句是 divi[cnt++] = divi[cnt - 1] + pi;
}

double idx;
bool cmp(const point a, const point b){
    double A = fabs(a.x - idx), B = fabs(b.x - idx);
    if(dcmp(A, B)) return dcmp(A, B) < 0;
    return a.id < b.id;
}

int n;
int find(double rad, int i)
{
    int pos = 0;
    for(int j=0; j<n; j++)
        if(j != i)
            tmp[pos] = rotate(P[j], rad), tmp[pos++].id = j;

    idx = rotate(P[i], rad).x;

    sort(tmp, tmp + pos, cmp);

    return tmp[0].id;
}


int main()
{
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%lf %lf", &P[i].x, &P[i].y);

    for(int i=0; i<n; i++)
    {
        cnt = 0;
        divi[cnt++] = 0;
        divi[cnt++] = pi * 2;
        for(int j=0; j<n; j++)
            if(i != j)
                for(int k=j + 1; k<n; k++)
                    if(k != i)
                    {
                        if(sign(cross(P[j] - P[i], P[k] - P[i]))== 0) continue;//不要也可以ac
                        add(P[k] - P[j]);
                        add((P[k] + P[j]) / 2 - P[i]);
                    }
        sort(divi, divi + cnt, less<double> ());

        for(int j=1; j<cnt; j++){
            double mid = (divi[j] + divi[j - 1]) / 2;
            ans[i][find(mid, i)] += (divi[j] - divi[j - 1]);
        }
    }

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
            printf("%.11f ", ans[i][j] / pi / 2);
        printf("\n");
    }

    system("pause");
    return 0;
}

C++ 解法, 执行用时: 49ms, 内存消耗: 584K, 提交时间: 2022-02-09 15:41:29

#include<bits/stdc++.h>
using namespace std;
const double Pi=acos(-1);
struct Point
{
    int x,y;
    Point operator +(const Point&a)const{return {x+a.x,y+a.y};}
    Point operator -(const Point&a)const{return {x-a.x,y-a.y};}
    double v_deg()const{return atan2(x,-y);}
};
int main()
{
    int n;scanf("%d",&n);
    vector<double> d,ans(n);
    vector<Point> a(n),b(n);
    for (auto &p:a) scanf("%d%d",&p.x,&p.y);
    auto Cross = [&](double x, double y, Point c) { return abs(x * c.x + y * c.y); };
    for(int i=0;i<n;++i)
    {
        ans.assign(n,0),d={-Pi,Pi};
        for(int j=0;j<n;++j)b[j]=a[j]-a[i];
        for(int j=0;j<n;++j)
            for(int k=j+1;k<n;++k)
            d.push_back((b[j]-b[k]).v_deg()),d.push_back((b[j]+b[k]).v_deg());
        for(auto t:d)d.push_back(t+(t<0?Pi:-Pi));
        sort(d.begin(),d.end());
        for(int t=1;t<d.size();++t)
        {
            if(d[t]-d[t-1]<1e-11)continue;
            int k=0;double L=d[t]-d[t-1], m=d[t-1]+L*0.5,x=cos(m),y=sin(m),mn=1e18,temp;
            for(int j=0;j<n;++j)
                if(j!=i&&mn-(temp=Cross(x,y,b[j]))>1e-9)mn=temp,k=j;
            ans[k]+=L;
        }
        for(int j=0;j<n;++j)
            printf("%.9f%c",i==j?0:ans[j]/Pi*0.5," \n"[j==n-1]);
    }
}