QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#785981#6812. Draw a triangleMartian148#WA 146ms3592kbC++201.9kb2024-11-26 19:47:212024-11-26 19:47:21

Judging History

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

  • [2024-11-26 19:47:21]
  • 评测
  • 测评结果:WA
  • 用时:146ms
  • 内存:3592kb
  • [2024-11-26 19:47:21]
  • 提交

answer

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

using i64 = long long;
typedef i64 ll;
using i128 = __int128;

constexpr int flg[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

struct Point {
    i128 x, y;
    Point(i128 x = 0, i128 y = 0) : x(x), y(y) {}
    bool operator == (Point &ohs) {
        return (x == ohs.x && y == ohs.y);
    }
};

typedef Point Vector;
Vector operator - (Vector A, Vector B) {return Vector(A.x - B.x, A.y - B.y);}

i128 cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x;}
i128 area2(Point A, Point B, Point C) {return cross(B - A, C - A);}

void print(i128 x) {
    if (x < 0) putchar('-'); x = -x;
    stack<int> st;
    do {
        st.push(x % 10);
        x /= 10;
    }while (x);
    while (!st.empty()) putchar(st.top() + '0'), st.pop();
}

void solve() {
    i64 x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
    Point A(x1, y1), B(x2, y2);
    
    i128 min_area2 = -1;
    Point C;

    auto calc = [&] (Point P) -> void {
        if (P == A || P == B) return ;
        i128 now_area = area2(A, B, P);
        if (now_area == 0) return ;
        if (now_area < 0) now_area = -now_area;
        if (min_area2 == -1 || now_area < min_area2) {
            min_area2 = now_area;
            C = P;
        }
    };
    
    Point P(Point((A.x + B.x) / 2, (A.y + B.y) / 2));

    for (int x = P.x - 10; x <= P.x + 10; x++)
        for (int y = P.y - 10; y <= P.y + 10; y++) {
            calc(Point(x, y));
        }

    // for (int k = 0; k < 4; k++) {
    //     calc(Point(A.x + flg[k][0], A.y + flg[k][1]));
    //     calc(Point(B.x + flg[k][0], B.y + flg[k][1]));
    // }

    i64 Cx = C.x, Cy = C.y;
    cout << Cx << " " << Cy << '\n';
    // i64 ar = min_area2;
    // cout << ar << '\n';
}

int main() {
    // freopen ("E.in", "r", stdin);
    // ios::sync_with_stdio(false);
    // cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while(T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3592kb

input:

3
1 0 1 4
0 1 0 9
0 0 2 2

output:

0 -8
-1 -5
-9 -8

result:

ok T=3 (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 146ms
memory: 3524kb

input:

50000
66620473 -33485015 66620223 -33485265
43307886 98029243 43307636 98028994
-88895230 -3180782 -88895480 -3181030
-90319745 20018595 -90319995 20018348
-56783257 84789686 -56783507 84789440
-81798038 90629147 -81798288 90628902
98942945 -939146 98942695 -939390
-42532151 -57203475 -42532401 -572...

output:

66620338 -33485149
43307751 98029109
-88895356 -3180907
-90319880 20018462
-56783383 84789562
-81798173 90629015
98942819 -939269
-42532286 -57203606
53500081 -30665727
27114919 46989004
-2657538 26865342
40614047 17923291
-47650030 96037591
92954160 -64535046
86508739 -51415285
-82017833 17392449
7...

result:

wrong answer wa on query #2 (test case 2)