QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#137437#2350. Integer Cowckz#TL 1786ms3740kbC++204.4kb2023-08-10 12:42:402023-08-10 12:42:44

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 12:42:44]
  • 评测
  • 测评结果:TL
  • 用时:1786ms
  • 内存:3740kb
  • [2023-08-10 12:42:40]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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...

output:


result: