結果
| 問題 |
No.2602 Real Collider
|
| コンテスト | |
| ユーザー |
 lumid
|
| 提出日時 | 2024-01-12 22:57:09 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,333 bytes |
| コンパイル時間 | 1,044 ms |
| コンパイル使用メモリ | 97,056 KB |
| 最終ジャッジ日時 | 2025-02-18 18:56:49 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 WA * 54 |
コンパイルメッセージ
main.cpp: In function ‘Circle welzl(const std::vector<Point>&)’:
main.cpp:160:19: warning: ‘void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Point*, vector<Point> >]’ is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
160 | random_shuffle(P_copy.begin(), P_copy.end());
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
from main.cpp:1:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
4581 | random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
| ^~~~~~~~~~~~~~
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}});
|
ソースコード
#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';
}
}