結果

問題 No.2602 Real Collider
コンテスト
ユーザー ぷら
提出日時 2024-01-12 23:25:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 8,781 bytes
コンパイル時間 1,814 ms
コンパイル使用メモリ 138,396 KB
最終ジャッジ日時 2025-02-18 19:11:17
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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";
        }
    }
}
0