QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#543227#8676. Three Kinds of DiceqwerasdfCompile Error//Python33.9kb2024-09-01 15:11:392024-09-01 15:11:39

Judging History

你现在查看的是最新测评结果

  • [2024-09-01 15:11:39]
  • 评测
  • [2024-09-01 15:11:39]
  • 提交

answer

//#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
//using namespace atcoder; //https://github.com/atcoder/ac-library

#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define bit(n, k) ((n >> k) & 1)
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<int, int> pii;

struct pt {
    long double x, y;
    bool operator == (pt const& t) const {
        return x == t.x && y == t.y;
    }
};

int orientation(pt a, pt b, pt c) {
    long double v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
    if (v < 0) return 1; // clockwise
    if (v > 0) return -1; // counter-clockwise
    return 0;
}

bool cw(pt a, pt b, pt c, bool include_collinear) {
    int o = orientation(a, b, c);
    return o < 0 || (include_collinear && o == 0);
}
bool collinear(pt a, pt b, pt c) { return orientation(a, b, c) == 0; }

void convex_hull(vector<pt>& a, bool include_collinear = false) {
    pt p0 = *min_element(a.begin(), a.end(), [](pt a, pt b) {
        return make_pair(a.y, a.x) < make_pair(b.y, b.x);
    });
    sort(a.begin(), a.end(), [&p0](const pt& a, const pt& b) {
        int o = orientation(p0, a, b);
        if (o == 0)
            return (p0.x-a.x)*(p0.x-a.x) + (p0.y-a.y)*(p0.y-a.y)
                < (p0.x-b.x)*(p0.x-b.x) + (p0.y-b.y)*(p0.y-b.y);
        return o < 0;
    });
    if (include_collinear) {
        int i = (int)a.size()-1;
        while (i >= 0 && collinear(p0, a[i], a.back())) i--;
        reverse(a.begin()+i+1, a.end());
    }

    vector<pt> st;
    for (int i = 0; i < (int)a.size(); i++) {
        while (st.size() > 1 && !cw(st[st.size()-2], st.back(), a[i], include_collinear))
            st.pop_back();
        st.push_back(a[i]);
    }

    if (include_collinear == false && st.size() == 2 && st[0] == st[1])
        st.pop_back();

    a = st;
}

void test_case(int tt){
    int n,m; cin>>n;
    vector<int> a(n);
    rep(i,0,n)cin>>a[i];
    cin>>m;
    vector<int> b(m);
    rep(i,0,m)cin>>b[i];
    sort(all(a));
    sort(all(b));
    ll sum=0;
    rep(i,0,n){
        int small=upper_bound(all(b),a[i-1])-lower_bound(all(b),1);
        int same=upper_bound(all(b),a[i])-lower_bound(all(b),a[i]);
        sum+=2*small+same;
    }
    if(sum<(ll)n*m){
        swap(a,b);
        swap(n,m);
    }
    vector<int> v;
    rep(i,0,n)v.push_back(a[i]);
    rep(i,0,m)v.push_back(b[i]);
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    vector<int> w;
    if(v[0]>1)w.push_back(v[0]-1);
    rep(i,0,(int)v.size()){
        if(!w.empty() && w.back()+1<v[i])w.push_back(w.back()+1);
        w.push_back(v[i]);
    }
    w.push_back(w.back()+1);
    int N=(int)w.size();
    vector<pt> x(N);
    rep(i,0,N){
        int small1=upper_bound(all(a),w[i-1])-lower_bound(all(a),1);
        int same1=upper_bound(all(a),w[i])-lower_bound(all(a),w[i]);
        int small2=upper_bound(all(b),w[i-1])-lower_bound(all(b),1);
        int same2=upper_bound(all(b),w[i])-lower_bound(all(b),w[i]);
        x[i]={(small1+0.5*same1)/n,(small2+0.5*same2)/m};
    }
    vector<pt> orig=x;
    convex_hull(x);
    N=(int)x.size();
    long double ans=1.0;
    rep(i,0,N-1){
        int j=i+1;
        if(x[i].x>=0.5 || x[j].x<0.5)continue;
        ans=x[i].y+((x[j].y-x[i].y)/(x[j].x-x[i].x)*(0.5-x[i].x));
    }
    cout<<fixed<<setprecision(9)<<ans<<' ';
    x=orig;
    for(auto &[u,v]:x){
        swap(u,v);
        u=1-u;
        v=1-v;
    }
    reverse(all(x));
    convex_hull(x);
    N=(int)x.size();
    ans=1.0;
    rep(i,0,N-1){
        int j=i+1;
        if(x[i].x>=0.5 || x[j].x<0.5)continue;
        ans=x[i].y+((x[j].y-x[i].y)/(x[j].x-x[i].x)*(0.5-x[i].x));
    }
    cout<<fixed<<setprecision(9)<<1-ans<<'\n';
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    //cin>>t;
    rep(i, 1, t + 1)
    {
        test_case(i);
    }
    return 0;
}

详细

  File "answer.code", line 1
    //#include <atcoder/all>
    ^^
SyntaxError: invalid syntax