QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#137437 | #2350. Integer Cow | ckz# | TL | 1786ms | 3740kb | C++20 | 4.4kb | 2023-08-10 12:42:40 | 2023-08-10 12:42:44 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define all(a) (a).begin(),(a).end()
using namespace std;
const double eps = 1e-8;
const double PI = acos(-1);
struct Point{
double x, y;
bool operator==(const Point &a) const{
return (abs(x-a.x) <= eps && abs(y-a.y)<=eps);
}
Point operator - (const Point &a) const{
return {x-a.x,y-a.y};
}
Point operator + (const Point &a) const{
return {x+a.x,y+a.y};
}
Point operator * (const double k) const{
return {k * x, k * y};
}
Point operator / (const double k) const{
return {x / k, y / k};
}
double operator * (const Point &a) const{
return {x*a.x + y*a.y};
}
double operator ^ (const Point &a) const{
return {x*a.y - y*a.x};
}
double len2() const{
return (*this) * (*this);
}
double len() const{
return sqrt(len2());
}
double dis2(const Point &a)const{
return (a-(*this)).len2();
}
long double dis(const Point &a) const{
return sqrtl(dis2(a));
}
}cow, cao;
struct Line{
Point p, v;
double dis(const Point &a) const{
return abs((v^(a-p)) / v.len());
}
Point proj(const Point &a) const{
return p + v * ((v * (a-p)) / (v * v));
}
}l;
struct Circle{
Point c;
long double r;
bool operator==(const Circle &a) const {return c==a.c && abs(r-a.r)<=eps;}
// 点与圆的关系
// -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;
}
// 圆与圆关系
// -1 相同 | 0 相离 | 1 外切 | 2 相交 | 3 内切 | 4 内含
int relation(const Circle &a) const{
if (*this==a) return -1;
const long double d=c.dis(a.c);
if (d>r+a.r+eps) return 0;
if (abs(d-r-a.r)<=eps) return 1;
if (abs(d-abs(r-a.r))<=eps) return 3;
if (d<abs(r-a.r)-eps) return 4;
return 2;
}
// 直线与圆的交点
vector<Point> inter(const Line &l) const{
const long double d=l.dis(c);
const Point p=l.proj(c);
// cout << d << " " << p.x << " " << p.y << "TTTTTTTTT\n";
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);
// cout << l.v / l.v.len() << "caocaocao\n";
// cout << l.v.len() << "1111111111\n";
return vector<Point>{p-(l.v/l.v.len())*k,p+(l.v/l.v.len())*k};
}
}cy;
void solve(){
cin >> cao.x >> cao.y >> cy.r;
cy.c = cao;
cin >> cow.x >> cow.y;
l.p = cow;
l.v = (cao - cow);
Point tmp = cao - cow;
long long x2 = tmp.len2();
long long r2 = cy.r * cy.r;
if(x2 <= r2){
cout << 0 << "\n";
cout << cow.x << " " << cow.y << "\n";
return;
}
double midis = 1e22;
Point ansp;
vector<Point> it = cy.inter(l);
// cout << it[0].x << " " << it[0].y << " " << it[1].x << " " << it[1].y << "qwq\n";
for(int b = 0 ; b < it.size() ; b ++){
long long Lx = min(ceil(it[b].x - 2000), ceil(it[b].x + 2000));
long long Rx = max(ceil(it[b].x - 2000), ceil(it[b].x + 2000));
long long Ly = min(ceil(it[b].y - 2000), ceil(it[b].y + 2000));
long long Ry = max(ceil(it[b].y - 2000), ceil(it[b].y + 2000));
for(long long x = Lx; x <= Rx ; x ++){
for(long long y = Ly ; y <= Ry ; y ++){
double dis2 = (x - cao.x) * (x - cao.x) + (y - cao.y) * (y - cao.y);
if(dis2 <= r2){
double dds = (x - cow.x) * (x - cow.x) + (y - cow.y) * (y - cow.y);
if(dds < midis){
midis = dds;
ansp.x = x;
ansp.y = y;
}
}
}
}
}
cout << "1\n";
cout << cow.x << " " << cow.y << " " << ansp.x << " " << ansp.y << "\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int t = 1;
cin >> t;
while(t--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 44ms
memory: 3708kb
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: 3648kb
input:
1 0 0 1 0 0
output:
0 0 0
result:
ok correct (1 test case)
Test #3:
score: 0
Accepted
time: 1786ms
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
Time Limit Exceeded
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...