QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#137616#2350. Integer Cowdzy521WA 1ms3848kbC++235.1kb2023-08-10 14:41:402023-08-10 14:41:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-10 14:41:56]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3848kb
  • [2023-08-10 14:41:40]
  • 提交

answer

#define _CRT_SEstartE_NO_DEPRECATE
#pragma warning(disable : 4996)
#include <map>
#include <unordered_map>
#include <set>
#include <fstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <bits/stdc++.h>
#define ACcode ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
const ll maxn = 1e6 + 7;
const ll maxm = 7e6 + 7;
constexpr ll mod = 998244353;
const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int Prime = 100007;
const double eps = 1e-10;
const double pi = acos(-1.0);
using namespace std;

using point_t = long double;
template <typename T>
struct point
{
    T x, y;
    point() {}
    point(T _x, T _y) { x = _x, y = _y; }
    point operator+(const point &b) const { return {x + b.x, y + b.y}; }
    point operator-(const point &b) const { return {x - b.x, y - b.y}; }
    point operator/(const T &k) const { return {x / k, y / k}; }
    point operator*(const T &k) const { return {x * k, y * k}; }
    T operator*(const point &b) const { return (x * b.x + y * b.y); }
    T operator^(const point &b) const { return x * b.y - y * b.x; }
    // 浮点数运算
    T len2() const { return (*this) * (*this); }
    T dis2(const point &a) const { return (a - (*this)).len2(); }
    long double len() const { return sqrtl(len2()); }
    long double dis(const point &a) const { return sqrtl(dis2(a)); }
};
using Point = point<point_t>;
template <typename T>
struct line
{
    point<T> p, v; // 直线上一点和方向向量
    line() {}
    line(T k, T b) { p = {0, b}, v = {1, k}; }
    line(point<T> _p, point<T> _v) { p = _p, v = _v; }
    point<T> proj(const point<T> &a) const // 点在直线上的投影
    {
        return p + v * ((v * (a - p)) / (v * v));
    }
    long double dis(const point<T> &a) const // 点到直线距离
    {
        return abs(v ^ (a - p)) / v.len();
    }
};
using Line = line<point_t>;
struct Circle
{
    Point c;
    long double r;
    // 点与圆的关系
    // -1 圆上 | 0 圆外 | 1 圆内
    int is_in(const Point &p) const
    {
        const long double d = p.dis(c);
        return abs(d - r) <= eps ? -1 : d < r - eps;
    }
    // 直线与圆关系
    // 0 相离 | 1 相切 | 2 相交
    int relation(const Line &l) const
    {
        const long double d = l.dis(c);
        if (d > r + eps)
            return 0;
        if (abs(d - r) <= eps)
            return 1;
        return 2;
    }
    // 直线与圆的交点
    vector<Point> inter(const Line &l) const
    {
        const long double d = l.dis(c);
        const Point p = l.proj(c);
        const int t = relation(l);
        if (t == 0)
            return vector<Point>();
        if (t == 1)
            return vector<Point>{p};
        const long double k = sqrt(r * r - d * d);
        return vector<Point>{p - (l.v / l.v.len()) * k, p + (l.v / l.v.len()) * k};
    }
};

void solve()
{
    // cout << fixed << setprecision(0);
    Point pc;
    Circle cir;
    cin >> cir.c.x >> cir.c.y >> cir.r >> pc.x >> pc.y;
    if (cir.is_in(pc) != 0)
    {
        cout << 0 << '\n';
        cout << pc.x << " " << pc.y << '\n';
        return;
    }
    Line l1(pc, {pc.x - cir.c.x, pc.y - cir.c.y});
    vector<Point> temp = cir.inter(l1);
    Point cro;
    if (pc.dis2(temp[0]) < pc.dis2(temp[1]))
        cro = temp[0];
    else
        cro = temp[1];
    Point ans;
    ll ansdis = 4e18;
    for (ll x = max(cir.c.x - cir.r, cro.x - 100000); x <= min(cir.c.x + cir.r, cro.x + 100000); x++)
    {
        if (cro.y >= cir.c.y)
        {
            ll l = cir.c.y, r = 3e9;
            while (l < r)
            {
                ll mid = l + r >> 1;
                Point now(x, mid);
                if (cir.c.dis2(now) <= cir.r * cir.r)
                    l = mid + 1;
                else
                    r = mid;
            }
            // cout << l << '\n';
            Point now(x, l - 1);
            ll dis2 = pc.dis2(now);
            if (dis2 < ansdis)
                ans = now, ansdis = dis2;
        }
        else
        {
            ll l = -3e9, r = cir.c.y;
            while (l < r)
            {
                ll mid = l + r >> 1;
                Point now(x, mid);
                if (cir.c.dis2(now) < cir.r * cir.r)
                    r = mid;
                else
                    l = mid + 1;
            }
            Point now(x, l);
            ll dis2 = pc.dis2(now);
            if (dis2 < ansdis)
                ans = now, ansdis = dis2;
        }
    }
    cout << 1 << '\n';
    cout << pc.x << " " << pc.y << " " << ans.x << " " << ans.y << '\n';
}

signed main()
{
    ACcode;
    // freopen("house.in", "r", stdin);
    // freopen("house.out", "w", stdout);
    int t = 1;
    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: 3776kb

input:

3
1 2 1 1 2
3 2 5 -10 3
0 0 1 10 0

output:

0
1 2
1
-10 3 -2 2
1
10 0 1 0

result:

ok correct (3 test cases)

Test #2:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

1
0 0 1 0 0

output:

0
0 0

result:

ok correct (1 test case)

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3848kb

input:

100
-1 0 2 -3 -2
0 -2 2 -2 0
2 -1 1 0 1
-1 -3 1 -1 0
-1 2 2 -1 -1
2 -2 2 0 -3
-2 -3 2 -3 -2
0 1 2 2 1
-1 0 1 -2 -2
2 -2 2 -1 -2
1 2 2 -2 2
-1 2 1 -1 2
-2 1 2 -3 -2
-1 1 1 -1 1
2 2 1 1 -3
2 0 1 -2 -1
-1 2 1 -2 0
2 -2 2 -2 -1
-2 -2 1 1 -2
-1 1 2 2 1
2 -3 1 0 -1
-3 -3 2 2 -1
2 1 1 -1 1
-3 -2 1 -2 -3
0 ...

output:

1
-3 -2 -2 -1
1
-2 0 -1 -1
1
0 1 1 -1
1
-1 0 -1 -2
1
-1 -1 -1 1
1
0 -3 0 -2
0
-3 -2
0
2 1
1
-2 -2 -2 0
1
-1 -2 0 -2
1
-2 2 -1 2
0
-1 2
1
-3 -2 -3 0
0
-1 1
1
1 -3 1 2
1
-2 -1 1 0
1
-2 0 -2 2
1
-2 -1 0 -2
1
1 -2 -1 -2
1
2 1 1 1
1
0 -1 1 -3
1
2 -1 -1 -3
1
-1 1 1 1
1
-2 -3 -2 -2
0
-2 -2
0
-2 -2
0
1 -1
1...

result:

wrong answer the distance of your solution has travelled is longer than expected. (test case 5)