QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#313977#784. 旋转卡壳nmmCampPTCP0 0ms0kbC++175.5kb2024-01-25 10:59:372024-01-25 10:59:39

Judging History

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

  • [2024-10-16 12:18:36]
  • hack成功,自动添加数据
  • (/hack/1005)
  • [2024-09-24 16:55:39]
  • hack成功,自动添加数据
  • (/hack/888)
  • [2024-07-31 21:52:32]
  • hack成功,自动添加数据
  • (/hack/764)
  • [2024-07-31 21:47:53]
  • hack成功,自动添加数据
  • (/hack/763)
  • [2024-05-30 09:00:15]
  • hack成功,自动添加数据
  • (/hack/642)
  • [2024-01-25 10:59:39]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-01-25 10:59:37]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using LD = long double;

constexpr LD eps = 1e-12;
const LD PI = acos(-1);
LD sgn(LD x){
    if(fabs(x) < eps) return 0;
    else return x>0 ? 1 : -1;
}
#define lt(x,y) (sgn((x)-(y)) < 0)
#define eq(x,y) (sgn((x)-(y)) == 0)
#define gt(x,y) (sgn((x)-(y)) > 0)
#define sqr(x) ((x)*(x))

//点的定义
struct pt{
    LD x,y;

    pt(LD x=0, LD y=0):x(x), y(y){};
    bool operator==(const pt& o){
        return sgn(x-o.x)==0 and sgn(y-o.y)==0;  //这里不能用not运算,非整数
    }
    bool operator!=(const pt& o){
        return !(*this == o);
    }
    pt operator+(const pt& o) const {
        return {x+o.x, y+o.y};
    }
    pt operator-(const pt& o) const {
        return {x-o.x, y-o.y};
    }
    pt operator*(LD c){
        return {x*c, y*c};
    }
    pt operator/(LD c){
        assert(c!=0);
        return {x/c, y/c};
    }
    pt operator+=(const pt& o){
        *this = *this + o;
    }
    pt operator-=(const pt& o){
        *this = *this - o;

    }
};
LD dis(pt a, pt b){
    return hypot(a.x-b.x, a.y-b.y);
}


//向量定义
typedef pt vec;
LD dot(vec a, vec b){
    return a.x*b.x + a.y*b.y;
}
LD cross(vec a, vec b){
    return a.x*b.y - a.y*b.x;
}
LD len(vec v){
    return sqrt(sqr(v.x) + sqr(v.y));
}
bool parallel(vec a, vec b){
    return sgn(cross(a, b)) == 0;
}
vec normalize(vec v){
    return v/len(v);
}
vec rotate(vec v, LD rad){
    return {v.x*cos(rad)-v.y*sin(rad), v.x*sin(rad)+v.y*cos(rad)};
}
vec rotate90(vec v){
    return {-v.y, v.x};
}
LD v_ang(vec a, vec b){
    return acos(dot(a,b)/len(a)/len(b));
}
LD tri_area(pt a, pt b, pt c){
    return fabs(cross(b-a, c-a)/2);
}

int qua(pt p){
    auto [x,y] = p;
    if(x > 0 and y >= 0) return 1;
    if(x <= 0 and y > 0) return 2;
    if(x < 0 and y <= 0) return 3;
    if(x >= 0 and y < 0) return 4;
    return 0;
}
bool cmp(pt x, pt y){
    return qua(x)<qua(y) or qua(x) == qua(y) and gt(cross(x,y), 0);  //叉乘为正,说明x到y为逆时针
}

vector<pair<int, int>>v[2];
vector<pt> mkv(vector<vector<pt>> a){
    for(int i = 0; i<2; ++i){
        a[i].emplace_back(a[i].front());
    }
    int i[2] = {0, 0},
        len[2] = {(int)a[0].size()-1, (int)a[1].size()-1};
    vector<pt>ret;
    vector<vec>e[2];
    for(int x = 0; x<2; ++x){
        for(int j = 1; j<a[x].size(); ++j){
            e[x].emplace_back(a[x][j]-a[x][j-1]);
        }
    }
    ret.emplace_back(a[0][0] + a[1][0]);
    do{
        int d = sgn(cross(a[1][i[1]+1] - a[1][i[1]],
                          a[0][i[0]+1] - a[0][i[0]])) >= 0;
        ret.emplace_back(a[d][i[d]+1] - a[d][i[d]] + ret.back());
//        if(a[d][i[d]+1]-a[d][i[d]] != e[d][i[d]]){
//            cout << "diff=" << ' ' << i[d] << ' ';
//        }
        v[1].emplace_back(d, i[d]);
        i[d] = (i[d]+1) % len[d];
    } while(i[0] or i[1]);
    return ret;
}
//int db1, db2, db3, db4;
vector<pt> minkovski(vector<pt> h1, vector<pt> h2){  //首尾相连,有封闭点(多余的p[0])
    vector<pt>res {h1[0]+h2[0]};
    h1.emplace_back(h1.front()), h2.emplace_back(h2.front());
    vector<vec>e1, e2;
    //n, m 分别为原凸包 A/B 的点集大小
    for(int i = 1; i<h1.size(); ++i) e1.emplace_back(h1[i]-h1[i-1]);
    for(int i = 1; i<h2.size(); ++i) e2.emplace_back(h2[i]-h2[i-1]);

//    db1 = e1.size();
//    db2 = e2.size();

    cout << "esize=" << e1.size() << ' ' << e2.size() << '\n';
    int n = h1.size()-1, m = h2.size()-1;
    int p1 = 0, p2 = 0;
    while(p1 < n and p2 < m){
        auto cur = res.back();
        if(sgn(cross(e1[p1], e2[p2])) >= 0) v[0].emplace_back(0, p1), cur += e1[p1++];
        else v[0].emplace_back(1, p2), cur += e2[p2++];
        res.emplace_back(cur);
    }
    while(p1 < n) v[0].emplace_back(0, p1), res.emplace_back(res.back()+e1[p1++]);
    while(p2 < m) v[0].emplace_back(1, p2), res.emplace_back(res.back()+e2[p2++]);

    return res;  //返回的为非严格凸包
}

void rotate(vector<pt>& v){
    auto p = min_element(v.begin(), v.end(), [](auto p1, auto p2){
        return p1.y < p2.y or p1.y == p2.y and p1.x < p2.x;
    })-v.begin();
    for(int i = 0; i<p; ++i) v.emplace_back(v[i]);
    v.erase(v.begin(), v.begin()+p);
}

int main(){
    int n; cin >> n;
    vector<pt>ps(n), fps(n);
    for(int i = 0; i<n; ++i){
        cin >> ps[i].x >> ps[i].y;
        fps[i] = pt{0,0}-ps[i];
    }
    rotate(ps), rotate(fps);
//    ps.emplace_back(ps[0]), fps.emplace_back(fps[0]);
    auto M1 = minkovski(ps, fps);
    auto M2 = mkv({ps, fps});
//    cout << M1.size() << '/' << M2.size() << '\n';
//    assert(M1.size() == M2.size());
//    for(int i = 0; i<M1.size(); ++i){
//        if(M1[i] != M2[i]) {
//            cout << i << ' ' << M1[i].x << ' ' << M1[i].y << ' ' << M2[i].x << ' ' << M2[i].y << '\n';
//            break;
//        }
    if(v[0].size() != v[1].size()){
        cout << v[0].size() << ' ' << v[1].size() << '\n';
        cout << "opns\n";
    }
    else{
        cout << "opsize= " << v[0].size() << '\n';
        for(int i = 0; i<v[0].size(); ++i){
            if(v[0][i] != v[1][i]){
                cout << i << ' ' << v[0][i].first << ' ' << v[0][i].second << ' ' << v[1][i].first << ' ' << v[1][i].second << '\n';
                break;
            }
        }
    }
    LD ans = 0;
    cout << M1.size() << ' ' << M2.size() << '\n';
    for(int i = 0; i<M1.size(); ++i){
        ans = max(ans, len(M1[i]));
    }
    cout << fixed << setprecision(10) << ans;
    return 0;
}




Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

1000
0 0
-997615 -8573
-1988394 -28911
-2726572 -44296
-3491635 -60392
-4419752 -82814
-5298550 -105946
-5723430 -118453
-6608257 -147267
-7034966 -161982
-7563964 -181682
-8507871 -222865
-9499799 -271846
-10090186 -303547
-10400262 -322989
-10614073 -339725
-11081438 -378596
-11791568 -439127
-127...

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%