#943762 (C++17) No.2602 Real Collider

提出ソース

結果

問題	No.2602 Real Collider
ユーザー	ぷら
提出日時	2024-01-12 23:25:20
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	8,781 bytes
コンパイル時間	1,665 ms
コンパイル使用メモリ	142,676 KB
実行使用メモリ	6,676 KB
最終ジャッジ日時	2024-01-12 23:25:27
合計ジャッジ時間	6,719 ms
ジャッジサーバーID （参考情報）	judge15 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,548 KB
testcase_01	AC	2 ms 6,548 KB
testcase_02	AC	2 ms 6,548 KB
testcase_03	AC	2 ms 6,548 KB
testcase_04	WA	-
testcase_05	AC	2 ms 6,548 KB
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	AC	19 ms 6,548 KB
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	AC	13 ms 6,548 KB
testcase_16	AC	21 ms 6,548 KB
testcase_17	AC	24 ms 6,548 KB
testcase_18	WA	-
testcase_19	WA	-
testcase_20	AC	27 ms 6,548 KB
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	AC	14 ms 6,548 KB
testcase_27	WA	-
testcase_28	AC	23 ms 6,548 KB
testcase_29	WA	-
testcase_30	WA	-
testcase_31	AC	21 ms 6,548 KB
testcase_32	AC	18 ms 6,548 KB
testcase_33	AC	21 ms 6,548 KB
testcase_34	AC	21 ms 6,548 KB
testcase_35	AC	14 ms 6,548 KB
testcase_36	AC	14 ms 6,548 KB
testcase_37	AC	23 ms 6,548 KB
testcase_38	AC	24 ms 6,548 KB
testcase_39	AC	23 ms 6,548 KB
testcase_40	AC	12 ms 6,548 KB
testcase_41	AC	25 ms 6,548 KB
testcase_42	AC	20 ms 6,548 KB
testcase_43	AC	21 ms 6,548 KB
testcase_44	AC	26 ms 6,548 KB
testcase_45	AC	16 ms 6,548 KB
testcase_46	AC	16 ms 6,548 KB
testcase_47	AC	24 ms 6,548 KB
testcase_48	AC	18 ms 6,548 KB
testcase_49	AC	16 ms 6,548 KB
testcase_50	AC	13 ms 6,548 KB
testcase_51	AC	13 ms 6,548 KB
testcase_52	AC	10 ms 6,548 KB
testcase_53	AC	21 ms 6,548 KB
testcase_54	AC	17 ms 6,548 KB
testcase_55	AC	19 ms 6,548 KB
testcase_56	AC	18 ms 6,548 KB
testcase_57	AC	18 ms 6,548 KB
testcase_58	AC	7 ms 6,548 KB
testcase_59	AC	20 ms 6,548 KB
testcase_60	AC	19 ms 6,548 KB
testcase_61	AC	15 ms 6,548 KB
testcase_62	AC	22 ms 6,548 KB
testcase_63	AC	24 ms 6,548 KB
testcase_64	AC	28 ms 6,548 KB
testcase_65	AC	15 ms 6,548 KB
testcase_66	AC	23 ms 6,548 KB
testcase_67	AC	12 ms 6,548 KB
testcase_68	AC	13 ms 6,548 KB
testcase_69	AC	10 ms 6,548 KB
testcase_70	AC	11 ms 6,548 KB
testcase_71	AC	14 ms 6,548 KB
testcase_72	AC	21 ms 6,548 KB
testcase_73	AC	17 ms 6,548 KB
testcase_74	AC	22 ms 6,548 KB
testcase_75	AC	23 ms 6,548 KB
testcase_76	AC	20 ms 6,548 KB
testcase_77	AC	21 ms 6,548 KB
testcase_78	AC	26 ms 6,548 KB
testcase_79	AC	23 ms 6,548 KB
testcase_80	AC	26 ms 6,548 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <string.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

namespace Geometry {
const double eps = 0.0000000001;
int sgn(double a) {
    if (a < -eps) return -1;
    if (a > eps) return 1;
    return 0;
}
struct Point {
    double x, y;
    Point() { x = 0, y = 0; }
    Point(double a, double b) { x = a, y = b; }
    Point operator-() { return {-x, -y}; }
    Point operator+(Point other) { return {x + other.x, y + other.y}; }
    Point operator-(Point other) { return {x - other.x, y - other.y}; }
    Point operator*(Point other) { return {x * other.x, y * other.y}; }
    Point operator/(Point other) { return {x / other.x, y / other.y}; }
    double length() { return sqrt(x * x + y * y); }
    Point normalized() { return {x / length(), y / length()}; }
    Point normalUnitVector() { return {-normalized().y, normalized().x}; }
    Point rotation(double arg) {
        double cs = cos(arg), sn = sin(arg);
        return Point(x * cs - y * sn, x * sn + y * cs);
    }
    double angle() { return atan2(y, x); }
    double dot(Point other) { return x * other.x + y * other.y; }
    double cross(Point other) { return x * other.y - y * other.x; }
    double distanceFrom(Point other) { return (other - (*this)).length(); }
};
Point operator*(Point a, double b) { return {a.x * b, a.y * b}; }
Point operator*(double a, Point b) { return {b.x * a, b.y * a}; }
Point operator/(Point a, double b) { return {a.x / b, a.y / b}; }
Point operator/(double a, Point b) { return {b.x / a, b.y / a}; }
bool operator==(Point a,Point b) { return sgn(a.x-b.x) == 0 && sgn(a.y-b.y) == 0; }
bool operator<(Point a, Point b) {
    if (sgn(a.x - b.x) != 0) return sgn(a.x - b.x) < 0;
    return sgn(a.y - b.y) < 0;
}
/*
3点A, B, Cの位置関係を返す関数 A, Bがすべて異なった点であるのが前提
//ABから見てBCは左に曲がるのなら +1
//ABから見てBCは右に曲がるのなら -1
//ABC(CBA)の順番で一直線上に並ぶなら +2
//ACB(BCA)の順番で一直線上に並ぶなら 0
BAC(CAB)の順番で一直線上に並ぶなら -2
*/
int iSP(Point a, Point b, Point c) {
    int flg = sgn((b - a).cross(c - a));
    if (flg == 1)
        return +1;
    else if (flg == -1)
        return -1;
    else {
        // ABC(CBA)
        if (sgn((b - a).dot(c - b)) > 0) return +2;
        // BAC(CAB)
        else if (sgn((a - b).dot(c - a)) > 0)
            return -2;
        // ACB(BCA)　CがA or Bと一致しても、こっちに含まれる。
        return 0;
    }
}
// 角ABCが鋭角なら0、直角なら1、鈍角なら2を返す。
int angletype(Point a, Point b, Point c) {
    auto v = (a - b).dot(c - b);
    if (sgn(v) > 0)
        return 0;
    else if (sgn(v) == 0)
        return 1;
    return 2;
}
Point error_val(998244353,1000000007);

namespace line {
struct Line {
    // 直線の通る二点。有向直線でないのならば、beginやendに違いはない。
    Point begin, end;
    Line() { begin = Point(), end = Point(); }
    Line(Point b, Point e) { begin = b, end = e; }
    // ax+by+c=0
    Line(double a, double b, double c) {
        if (sgn(a) == 0 && sgn(b) == 0) {
            assert(-1);  // 警告を出してプログラムを終了させる。
        }
        if (sgn(b) == 0) {  // ax+c=0になる。
            begin = Point(-c / a, 0.0);
            end = Point(-c / a, 1.0);
        } else {
            // y=-(ax+c)/b　傾きは-a/bで、y切片が-c/b
            begin = Point(0, -c / b);
            end = Point(1.0, -(a + c) / b);
        }
    }
    Point vec() { return end - begin; }
    Point countervec() { return begin - end; }
};
// 半直線なら、Lineと同じだけど、はっきりと区別する。
typedef Line Ray;
// 線分の場合、Lineと同じものになるが、はっきりと区別する
typedef Line Segment;
// 直線の交点を返す。交わってなければ、error_valを返す
Point lineIntersection(Line l1, Line l2) {
    if (sgn(l1.vec().cross(l2.vec())) == 0) return error_val;
    Point ret;
    ret = l1.begin + l1.vec() * (l2.end - l1.begin).cross(l2.vec()) /
                                    l1.vec().cross(l2.vec());
    return ret;
}
// 線分が共通部分を持つかどうか？と線分の交点を返す。共通部分がない、もしくは交点が一意ではないなら、error_valを返す
// trueなら、共通部分を持つ。falseなら、共通部分を持たない。
pair<bool, Point> segmentIntersection(Segment s1, Segment s2) {
    if (iSP(s1.begin, s1.end, s2.begin) * iSP(s1.begin, s1.end, s2.end) <= 0 &&
        iSP(s2.begin, s2.end, s1.begin) * iSP(s2.begin, s2.end, s1.end) <= 0) {
        // 平行ならば、交点は定まらない。(完全に重なってるので)
        if (s1.vec().cross(s2.vec()) == 0)
            return make_pair(true, error_val);
        else  // そうでないのなら、lineIntersection()で交点を返しておく。
            return make_pair(true, lineIntersection(s1, s2));
    }
    return make_pair(false, error_val);
}
// 点と直線の距離。引数は、点、直線上の2点
double distanceBetweenPointAndLine(Point p, Line l) {
    return abs(l.vec().cross(p - l.begin) / l.vec().length());
}

// 点と半直線の距離。引数は、点、半直線(始点から終点方向に延びる)
double distanceBetweenPointAndRay(Point p, Ray r) {
    // 始点との距離のパターン
    if (sgn((p - r.begin).dot(r.vec())) < 0) return r.begin.distanceFrom(p);
    return abs(r.vec().cross(p - r.begin) / r.vec().length());
}
// 点と線分の距離。引数は、点、線分の両端
double distanceBetweenPointAndSegment(Point p, Segment s) {
    if (sgn(s.vec().dot(p - s.begin)) < 0 ||
        sgn(s.countervec().dot(p - s.end)) < 0) {
        // 下した垂線は線分の上にはない
        return min(p.distanceFrom(s.begin), p.distanceFrom(s.end));
    }
    return distanceBetweenPointAndLine(p, s);
}
// 二線分間の距離
double distanceBetweenSegmentAndSegment(const Segment& s1, const Segment& s2) {
    if (segmentIntersection(s1, s2).first) return 0;  // 交点を持つ
    double ans = distanceBetweenPointAndSegment(s1.begin, s2);
    ans = min(ans, distanceBetweenPointAndSegment(s1.end, s2));
    ans = min(ans, distanceBetweenPointAndSegment(s2.begin, s1));
    ans = min(ans, distanceBetweenPointAndSegment(s2.end, s1));
    return ans;
}
// 正射影
// 引数は点A, B, Cで、Aの直線BC上の正射影を求める。
Point projection(Point a, Line l) {
    Point ret;
    ret = l.begin +
          l.vec().normalized() * (a - l.begin).dot(l.vec()) / l.vec().length();
    return ret;
}
// 鏡映変換。引数は点A, B, Cで、直線BCにおいて、Aと線対称な点を求める。
Point reflection(Point a, Line l) {
    Point ret;
    ret = a + 2 * (projection(a, l) - a);
    return ret;
}
};  // namespace line

namespace circle {
    struct Circle {
        Point p;
        double r;
        Circle() {
            p = Point(),r = 0;
        }
        Circle(Point a,double b) {
            p = a,r = b;
        }
    };
};

// もうこんなの作ってられるか！！
// 参考:Senさんのブログ

};  // namespace Geometry

using namespace Geometry;

double pi = 3.14159265358979;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int Q;
    cin >> Q;
    int x1,y1,x2,y2,x3,y3;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
    if(make_pair(x1,y1) >= make_pair(x2,y2)) {
        swap(x1,x2);
        swap(y1,y2);
    }
    if(make_pair(x1,y1) >= make_pair(x3,y3)) {
        swap(x1,x3);
        swap(y1,y3);
    }
    if(make_pair(x2,y2) >= make_pair(x3,y3)) {
        swap(x2,x3);
        swap(y2,y3);
    }
    Point a(x1,y1),b(x2,y2),c(x3,y3);
    Point d = (a+b)/2,e = (b+c)/2;
    Point d2 = (a-d).rotation(pi/2)+d,e2 = (b-e).rotation(pi/2)+e;
    line::Line l1(d,d2),l2(e,e2);
    Point m = line::lineIntersection(l1,l2);
    double r = (m-a).length();
    if(!sgn(m.x-998244353)) {
        m = (a+c)/3;
        r = (m-a).length();
    }
    while(Q--) {
        int x,y;
        cin >> x >> y;
        Point now(x,y);
        double rn = (m-now).length();
        if(rn < r+eps) {
            cout << "Yes" << "\n";
        }
        else {
            cout << "No" << "\n";
        }
    }
}

yukicoder

結果

テストケース

ソースコード