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

提出ソース

結果

問題	No.2602 Real Collider
ユーザー	lumid
提出日時	2024-01-12 22:57:09
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	4,333 bytes
コンパイル時間	931 ms
コンパイル使用メモリ	93,172 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-09-27 23:44:36
合計ジャッジ時間	14,814 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	WA	-
testcase_05	WA	-
testcase_06	AC	2 ms 6,944 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	AC	189 ms 6,944 KB
testcase_13	AC	98 ms 6,944 KB
testcase_14	WA	-
testcase_15	AC	112 ms 6,940 KB
testcase_16	AC	166 ms 6,944 KB
testcase_17	WA	-
testcase_18	AC	130 ms 6,940 KB
testcase_19	WA	-
testcase_20	WA	-
testcase_21	AC	124 ms 6,944 KB
testcase_22	AC	151 ms 6,940 KB
testcase_23	AC	99 ms 6,940 KB
testcase_24	AC	143 ms 6,944 KB
testcase_25	AC	152 ms 6,940 KB
testcase_26	WA	-
testcase_27	AC	171 ms 6,944 KB
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	AC	202 ms 6,940 KB
testcase_39	WA	-
testcase_40	AC	88 ms 6,940 KB
testcase_41	WA	-
testcase_42	AC	172 ms 6,940 KB
testcase_43	WA	-
testcase_44	AC	217 ms 6,940 KB
testcase_45	AC	135 ms 6,940 KB
testcase_46	WA	-
testcase_47	WA	-
testcase_48	WA	-
testcase_49	WA	-
testcase_50	WA	-
testcase_51	WA	-
testcase_52	AC	69 ms 6,940 KB
testcase_53	WA	-
testcase_54	WA	-
testcase_55	AC	159 ms 6,944 KB
testcase_56	AC	146 ms 6,940 KB
testcase_57	AC	148 ms 6,944 KB
testcase_58	WA	-
testcase_59	WA	-
testcase_60	WA	-
testcase_61	WA	-
testcase_62	WA	-
testcase_63	WA	-
testcase_64	AC	238 ms 6,944 KB
testcase_65	WA	-
testcase_66	WA	-
testcase_67	AC	90 ms 6,940 KB
testcase_68	WA	-
testcase_69	WA	-
testcase_70	WA	-
testcase_71	WA	-
testcase_72	WA	-
testcase_73	WA	-
testcase_74	WA	-
testcase_75	WA	-
testcase_76	WA	-
testcase_77	WA	-
testcase_78	WA	-
testcase_79	WA	-
testcase_80	WA	-

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

コンパイルメッセージ

main.cpp: In function 'int main()':
main.cpp:169:26: warning: narrowing conversion of 'x1' from 'long double' to 'double' [-Wnarrowing]
  169 |     Circle mec = welzl({{x1,y1},{x2,y2},{x3,y3}});
      |                          ^~
main.cpp:169:29: warning: narrowing conversion of 'y1' from 'long double' to 'double' [-Wnarrowing]
  169 |     Circle mec = welzl({{x1,y1},{x2,y2},{x3,y3}});
      |                             ^~
main.cpp:169:34: warning: narrowing conversion of 'x2' from 'long double' to 'double' [-Wnarrowing]
  169 |     Circle mec = welzl({{x1,y1},{x2,y2},{x3,y3}});
      |                                  ^~
main.cpp:169:37: warning: narrowing conversion of 'y2' from 'long double' to 'double' [-Wnarrowing]
  169 |     Circle mec = welzl({{x1,y1},{x2,y2},{x3,y3}});
      |                                     ^~
main.cpp:169:42: warning: narrowing conversion of 'x3' from 'long double' to 'double' [-Wnarrowing]
  169 |     Circle mec = welzl({{x1,y1},{x2,y2},{x3,y3}});
      |                                          ^~
main.cpp:169:45: warning: narrowing conversion of 'y3' from 'long double' to 'double' [-Wnarrowing]
  169 |     Circle mec = welzl({{x1,y1},{x2,y2},{x3,y3}});
      |                                             ^~

ソースコード

raw source code

#include <algorithm>
#include <assert.h>
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
 
// Defining infinity
const double INF = 1e18;
 
// Structure to represent a 2D point
struct Point {
    double X, Y;
};
 
// Structure to represent a 2D circle
struct Circle {
    Point C;
    double R;
};
 
// Function to return the euclidean distance
// between two points
double dist(const Point& a, const Point& b)
{
    return sqrt(pow(a.X - b.X, 2)
                + pow(a.Y - b.Y, 2));
}
 
// Function to check whether a point lies inside
// or on the boundaries of the circle
bool is_inside(const Circle& c, const Point& p)
{
    return dist(c.C, p) <= c.R;
}
 
// The following two functions are used
// To find the equation of the circle when
// three points are given.
 
// Helper method to get a circle defined by 3 points
Point get_circle_center(double bx, double by,
                        double cx, double cy)
{
    double B = bx * bx + by * by;
    double C = cx * cx + cy * cy;
    double D = bx * cy - by * cx;
    return { (cy * B - by * C) / (2 * D),
             (bx * C - cx * B) / (2 * D) };
}
 
// Function to return a unique circle that
// intersects three points
Circle circle_from(const Point& A, const Point& B,
                   const Point& C)
{
    Point I = get_circle_center(B.X - A.X, B.Y - A.Y,
                                C.X - A.X, C.Y - A.Y);
 
    I.X += A.X;
    I.Y += A.Y;
    return { I, dist(I, A) };
}
 
// Function to return the smallest circle
// that intersects 2 points
Circle circle_from(const Point& A, const Point& B)
{
    // Set the center to be the midpoint of A and B
    Point C = { (A.X + B.X) / 2.0, (A.Y + B.Y) / 2.0 };
 
    // Set the radius to be half the distance AB
    return { C, dist(A, B) / 2.0 };
}
 
// Function to check whether a circle
// encloses the given points
bool is_valid_circle(const Circle& c,
                     const vector<Point>& P)
{
 
    // Iterating through all the points
    // to check  whether the points
    // lie inside the circle or not
    for (const Point& p : P)
        if (!is_inside(c, p))
            return false;
    return true;
}
 
// Function to return the minimum enclosing
// circle for N <= 3
Circle min_circle_trivial(vector<Point>& P)
{
    assert(P.size() <= 3);
    if (P.empty()) {
        return { { 0, 0 }, 0 };
    }
    else if (P.size() == 1) {
        return { P[0], 0 };
    }
    else if (P.size() == 2) {
        return circle_from(P[0], P[1]);
    }
 
    // To check if MEC can be determined
    // by 2 points only
    for (int i = 0; i < 3; i++) {
        for (int j = i + 1; j < 3; j++) {
 
            Circle c = circle_from(P[i], P[j]);
            if (is_valid_circle(c, P))
                return c;
        }
    }
    return circle_from(P[0], P[1], P[2]);
}
 
// Returns the MEC using Welzl's algorithm
// Takes a set of input points P and a set R
// points on the circle boundary.
// n represents the number of points in P
// that are not yet processed.
Circle welzl_helper(vector<Point>& P,
                    vector<Point> R, int n)
{
    // Base case when all points processed or |R| = 3
    if (n == 0 || R.size() == 3) {
        return min_circle_trivial(R);
    }
 
    // Pick a random point randomly
    int idx = rand() % n;
    Point p = P[idx];
 
    // Put the picked point at the end of P
    // since it's more efficient than
    // deleting from the middle of the vector
    swap(P[idx], P[n - 1]);
 
    // Get the MEC circle d from the
    // set of points P - {p}
    Circle d = welzl_helper(P, R, n - 1);
 
    // If d contains p, return d
    if (is_inside(d, p)) {
        return d;
    }
 
    // Otherwise, must be on the boundary of the MEC
    R.push_back(p);
 
    // Return the MEC for P - {p} and R U {p}
    return welzl_helper(P, R, n - 1);
}
 
Circle welzl(const vector<Point>& P)
{
    vector<Point> P_copy = P;
    random_shuffle(P_copy.begin(), P_copy.end());
    return welzl_helper(P_copy, {}, P_copy.size());
}
 
// Driver code
int main()
{
    int q;cin>>q;
    long double x1,y1,x2,y2,x3,y3;cin>>x1>>y1>>x2>>y2>>x3>>y3;
    Circle mec = welzl({{x1,y1},{x2,y2},{x3,y3}});
    while(q--){
        long double x,y;cin>>x>>y;
        cout<<(sqrtl((x-mec.C.X)*(x-mec.C.X)+(y-mec.C.Y)*(y-mec.C.Y))<=mec.R?"Yes":"No")<<'\n';
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード