QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#874477#8620. Jigsaw Puzzleucup-team6275Compile Error//C++205.1kb2025-01-28 06:47:352025-01-28 06:47:36

Judging History

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

  • [2025-01-28 06:47:36]
  • 评测
  • [2025-01-28 06:47:35]
  • 提交

answer

#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <iomanip>
#include <map>
#include <deque>
#include <set>
#include <cassert>
#include <cmath>
#include <complex>

using namespace std;
#define ld __float128
#define cmpl complex<ld>

struct vec {
    ld x, y;

    ld len() {
        return sqrt(x * x + y * y);
    }

    vec() {}

    vec(ld x, ld y) : x(x), y(y) {}
};

vec operator-(const vec& a, const vec& b) {
    return {a.x - b.x, a.y - b.y};
}

vec operator+(const vec& a, const vec& b) {
    return {a.x + b.x, a.y + b.y};
}

ld operator*(const vec& a, const vec& b) {
    return a.x * b.x + a.y * b.y;
}

struct Side {
    ld len;
    int num;
    int ind;
};

bool cmp(const Side& a, const Side& b) {
    return a.len < b.len;
}

const ld EPS = 1e-9;

void transform_to_point(vector <vec>& a, int ind, vec flex) {
    vec adding = flex - a[ind];
    for (auto& i : a) {
        i = i + adding;
    }
}

void transform_mul(vector <vec>& a, int ind, cmpl value) {

    int n = a.size();
    vector <vec> flex(n);

    for (int i = 0; i < n; ++i) {
        int ii = (i + 1) % n;
        flex[i] = (a[ii] - a[i]);
    }

    for (int it = 0; it < n - 1; ++it) {
        int i = (ind + it) % n;
        int ii = (i + 1) % n;

        cmpl xd = {flex[i].x, flex[i].y};
        xd *= value;
        a[ii] = a[i] + vec(xd.real(), xd.imag());
    }
}

bool validate(vector <vec>& a) {
    for (auto i : a) {
        if (i.x < -EPS || i.y < -EPS || i.x > 1 + EPS || i.y > 1 + EPS) return false;
    }
    return true;
}

void solve() {
    int n;
    cin >> n;

    vector <vector <vec>> a(n);
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        a[i].resize(k);
        for (int j = 0; j < k; ++j) {
            cin >> a[i][j].x >> a[i][j].y;
        }
    }

    vector <Side> sides;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < a[i].size(); ++j) {
            int jj = (j + 1) % a[i].size();
            ld flex = (a[i][jj] - a[i][j]).len();
            if (abs(flex - 1) < EPS) continue;
            sides.push_back({flex, i, j});
        }
    }
    sort(sides.begin(), sides.end(), cmp);
    map <pair <int, int>, vector <pair <int, int>>> g;

    for (int i = 0; i + 1 < sides.size(); ++i) {
        if (sides[i + 1].len - sides[i].len < EPS) {
            pair <int, int> t1 = {sides[i].num, sides[i].ind};
            pair <int, int> t2 = {sides[i + 1].num, sides[i + 1].ind};
            g[t1].push_back(t2);
            g[t2].push_back(t1);
        }
    }
    vector <int> used(n);
    vector <int> st;

    for (int i = 0; i < n; ++i) {
        int ln = a[i].size();
        for (int j = 0; j < a[i].size(); ++j) {
            vec vec1 = (a[i][(j + 1) % ln] - a[i][j]);
            vec vec2 = a[i][j] - (a[i][(j + ln - 1) % ln]);
            if (abs(vec1 * vec2) < EPS) {
                used[i] = 1;
                cmpl cha = {vec1.x, vec1.y};
                cha /= vec1.len();
                transform_mul(a[i], j, (cmpl)1 / cha);
                transform_to_point(a[i], j, vec(0, 0));
                used[i] = 1;
                st.push_back(i);
                assert(validate(a[i]));
                break;
            }
        }
        if (!st.empty()) break;
    }

    while (!st.empty()) {
        int v = st.back();
        st.pop_back();

        int ln = a[v].size();
        for (int i = 0; i < ln; ++i) {
            int ii = (i + 1) % ln;

            for (auto [vv, j] : g[make_pair(v, i)]) {
                if (used[vv]) continue;
                auto cop = a[vv];
                vec vec1 = (a[v][ii] - a[v][i]);
                int jj = (j + 1) % a[vv].size();
                vec vec2 = (a[vv][jj] - a[vv][j]);
                cmpl need_vec = -cmpl(vec1.x, vec1.y) / cmpl(vec2.x, vec2.y);
                transform_mul(a[vv], j, need_vec);
                transform_to_point(a[vv], j, a[v][ii]);

                if (!validate(a[vv])) {
                    a[vv] = cop;
                    continue;
                }

                used[vv] = 1;
                st.push_back(vv);
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        for (auto j : a[i]) {
            cout << fixed << setprecision(10) << j.x << " " << j.y << "\n";
        }
        cout << "\n";
    }
}

signed main() {
    if (1) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
    }
    int32_t t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

/*
 4
4
0.440405375916 0.778474079786
0.000000000000 0.090337001520
0.469097990019 0.000000000000
0.702887505082 0.689470121906
4
0.222810526978 0.000000000000
0.270828246634 0.522212063829
0.000000000000 0.547114887265
0.021480010612 0.069880870008
4
0.000000000000 0.312825941471
0.358219176380 0.000000000000
0.532830100286 0.122181578260
0.088431750275 0.414089758021
4
0.158867722074 0.061734605990
0.973532298476 0.000000000000
0.853551564066 0.712811281737
0.000000000000 0.569141075980
 */

Details

answer.code: In member function ‘__float128 vec::len()’:
answer.code:22:20: error: call of overloaded ‘sqrt(__float128)’ is ambiguous
   22 |         return sqrt(x * x + y * y);
      |                ~~~~^~~~~~~~~~~~~~~
In file included from /usr/include/features.h:502,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/c++config.h:680,
                 from /usr/include/c++/14/bits/requires_hosted.h:31,
                 from /usr/include/c++/14/iostream:38,
                 from answer.code:1:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:143:1: note: candidate: ‘double sqrt(double)’
  143 | __MATHCALL (sqrt,, (_Mdouble_ __x));
      | ^~~~~~~~~~
In file included from answer.code:11:
/usr/include/c++/14/cmath:446:3: note: candidate: ‘constexpr long double std::sqrt(long double)’
  446 |   sqrt(long double __x)
      |   ^~~~
/usr/include/c++/14/cmath:442:3: note: candidate: ‘constexpr float std::sqrt(float)’
  442 |   sqrt(float __x)
      |   ^~~~
answer.code: In function ‘void solve()’:
answer.code:98:17: error: no match for ‘operator>>’ (operand types are ‘std::istream’ {aka ‘std::basic_istream<char>’} and ‘__float128’)
   98 |             cin >> a[i][j].x >> a[i][j].y;
      |             ~~~ ^~
      |             |
      |             std::istream {aka std::basic_istream<char>}
In file included from /usr/include/c++/14/iostream:42:
/usr/include/c++/14/istream:170:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(bool&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’ (near match)
  170 |       operator>>(bool& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:170:7: note:   conversion of argument 1 would be ill-formed:
answer.code:98:28: error: cannot bind non-const lvalue reference of type ‘bool&’ to a value of type ‘__float128’
   98 |             cin >> a[i][j].x >> a[i][j].y;
/usr/include/c++/14/istream:174:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(short int&) [with _CharT = char; _Traits = std::char_traits<char>]’ (near match)
  174 |       operator>>(short& __n);
      |       ^~~~~~~~
/usr/include/c++/14/istream:174:7: note:   conversion of argument 1 would be ill-formed:
answer.code:98:28: error: cannot bind non-const lvalue reference of type ‘short int&’ to a value of type ‘__float128’
   98 |             cin >> a[i][j].x >> a[i][j].y;
/usr/include/c++/14/istream:177:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(short unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’ (near match)
  177 |       operator>>(unsigned short& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:177:7: note:   conversion of argument 1 would be ill-formed:
answer.code:98:28: error: cannot bind non-const lvalue reference of type ‘short unsigned int&’ to a value of type ‘__float128’
   98 |             cin >> a[i][j].x >> a[i][j].y;
/usr/include/c++/14/istream:181:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(int&) [with _CharT = char; _Traits = std::char_traits<char>]’ (near match)
  181 |       operator>>(int& __n);
      |       ^~~~~~~~
/usr/include/c++/14/istream:181:7: note:   conversion of argument 1 would be ill-formed:
answer.code:98:28: error: cannot bind non-const lvalue reference of type ‘int&’ to a value of type ‘__float128’
   98 |             cin >> a[i][j].x >> a[i][j].y;
/usr/include/c++/14/istream:184:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’ (near match)
  184 |       operator>>(unsigned int& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:184:7: note:   conversion of argument 1 would be ill-formed:
answer.code:98:28: error: cannot bind non-const lvalue reference of type ‘unsigned int&’ to a value of type ‘__float128’
   98 |             cin >> a[i][j].x >> a[i][j].y;
/usr/include/c++/14/istream:188:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’ (near match)
  188 |       operator>>(long& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:188:7: note:   conversion of argument 1 would be ill-formed:
answer.code:98:28: error: cannot bind non-const lvalue reference of type ‘long int&’ to a value of type ‘__float128’
   98 |             cin >> a[i][j].x >> a[i][j].y;
/usr/include/c++/14/istream:192:7: note: candidate: ‘std::basic_istream...