QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#137613 | #2350. Integer Cow | dzy521 | WA | 1ms | 3704kb | C++23 | 5.1kb | 2023-08-10 14:40:25 | 2023-08-10 14:40:26 |
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);
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: 0
Wrong Answer
time: 1ms
memory: 3704kb
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 3 1 10 0 1 1
result:
wrong answer the destination point isn't inside the circle. (test case 2)