QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#137614 | #2350. Integer Cow | dzy521 | WA | 1ms | 3740kb | C++23 | 5.1kb | 2023-08-10 14:41:00 | 2023-08-10 14:41:04 |
Judging History
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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3736kb
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: 0ms
memory: 3732kb
input:
1 0 0 1 0 0
output:
0 0 0
result:
ok correct (1 test case)
Test #3:
score: 0
Accepted
time: 1ms
memory: 3740kb
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 0 1 0 -3 0 -2 0 -3 -2 0 2 1 1 -2 -2 -1 -1 1 -1 -2 0 -2 1 -2 2 -1 2 0 -1 2 1 -3 -2 -2 -1 0 -1 1 1 1 -3 2 1 1 -2 -1 1 0 1 -2 0 -1 1 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 -3 -3 0 -2 -2 0 -2 -2 0 1 -1...
result:
ok correct (100 test cases)
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3664kb
input:
100 -5 9 1 -2 -7 3 1 6 9 2 -2 -1 2 -7 3 -10 -8 7 -8 6 0 3 9 -6 -7 6 4 9 -1 4 8 6 7 -7 7 3 -7 7 2 0 -5 -1 6 -7 -7 -5 8 7 -9 -6 -6 -5 5 -10 -9 -7 1 9 7 -2 -4 9 4 8 3 3 -9 6 2 -2 -1 -7 3 -8 2 -2 -5 4 -1 0 1 2 9 -5 5 0 9 5 -4 -1 -10 8 2 -3 -7 -8 -3 3 2 -3 3 3 7 -4 6 6 0 6 -3 5 -7 5 9 9 9 2 0 2 8 -10 2 1...
output:
1 -2 -7 -5 8 1 9 2 9 1 1 -7 3 -4 -1 1 -8 6 -10 -1 1 -6 -7 -4 -5 0 -1 4 1 -7 7 1 6 1 2 0 2 -1 1 -7 -7 -7 -6 1 -9 -6 -8 2 1 -10 -9 -10 -8 1 7 -2 2 1 1 8 3 -1 7 1 2 -2 3 -3 1 -8 2 -3 -5 1 -1 0 -2 -1 0 -5 5 1 -4 -1 -3 5 1 -3 -7 -10 6 1 2 -3 -5 -3 1 -4 6 -3 6 1 -3 5 1 3 1 9 9 1 9 1 8 -10 2 -2 1 7 -1 5 1 ...
result:
wrong answer the distance of your solution has travelled is longer than expected. (test case 60)