QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#137418 | #2350. Integer Cow | ckz# | WA | 7ms | 3736kb | C++20 | 4.3kb | 2023-08-10 12:20:47 | 2023-08-10 12:20:59 |
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 {k / x, k / y};
}
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;}
long double circ() const {return 2*PI*r;} // 周长
long double area() const {return PI*r*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;
}
// 圆与圆关系
// -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);
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};
}
}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);
for(int b = 0 ; b < it.size() ; b ++){
long long Lx = min(ceil(it[b].x - 1000), ceil(it[b].x + 1000));
long long Rx = max(ceil(it[b].x - 1000), ceil(it[b].x + 1000));
long long Ly = min(ceil(it[b].y - 1000), ceil(it[b].y + 1000));
long long Ry = max(ceil(it[b].y - 1000), ceil(it[b].y + 1000));
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 7ms
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 -2 0
result:
wrong answer the destination point isn't inside the circle. (test case 3)