fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iomanip>
  6.  
  7. using namespace std;
  8.  
  9. struct Point {
  10.     double x, y;
  11.     Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
  12. };
  13.  
  14. struct Circle {
  15.     Point center;
  16.     double radius;
  17.     Circle(Point c = Point(0, 0), double r = 0) : center(c), radius(r) {}
  18.  
  19.     // 检查点是否在圆内（包括圆上）
  20.     bool contains(const Point& p) const {
  21.         double dx = p.x - center.x;
  22.         double dy = p.y - center.y;
  23.         return dx*dx + dy*dy <= radius*radius + 1e-9;  // 添加微小误差容限
  24.     }
  25. };
  26.  
  27. // 计算两点之间的距离
  28. double distance(const Point& a, const Point& b) {
  29.     double dx = a.x - b.x;
  30.     double dy = a.y - b.y;
  31.     return sqrt(dx*dx + dy*dy);
  32. }
  33.  
  34. // 计算三个点的外接圆
  35. Circle circleFrom3Points(const Point& a, const Point& b, const Point& c) {
  36.     // 检查三点是否共线
  37.     double area = a.x*(b.y - c.y) + b.x*(c.y - a.y) + c.x*(a.y - b.y);
  38.     if (fabs(area) < 1e-9) {
  39.         // 共线，返回包含这三点的最小圆（实际上是直径）
  40.         double d1 = distance(a, b);
  41.         double d2 = distance(b, c);
  42.         double d3 = distance(a, c);
  43.  
  44.         if (d1 >= d2 && d1 >= d3) {
  45.             return Circle(Point((a.x + b.x)/2, (a.y + b.y)/2), d1/2);
  46.         } else if (d2 >= d1 && d2 >= d3) {
  47.             return Circle(Point((b.x + c.x)/2, (b.y + c.y)/2), d2/2);
  48.         } else {
  49.             return Circle(Point((a.x + c.x)/2, (a.y + c.y)/2), d3/2);
  50.         }
  51.     }
  52.  
  53.     // 计算外接圆圆心（垂直平分线交点）
  54.     double d = 2 * (a.x*(b.y - c.y) + b.x*(c.y - a.y) + c.x*(a.y - b.y));
  55.     double ux = ((a.x*a.x + a.y*a.y)*(b.y - c.y) + 
  56.                 (b.x*b.x + b.y*b.y)*(c.y - a.y) + 
  57.                 (c.x*c.x + c.y*c.y)*(a.y - b.y)) / d;
  58.     double uy = ((a.x*a.x + a.y*a.y)*(c.x - b.x) + 
  59.                 (b.x*b.x + b.y*b.y)*(a.x - c.x) + 
  60.                 (c.x*c.x + c.y*c.y)*(b.x - a.x)) / d;
  61.  
  62.     Point center(ux, uy);
  63.     double radius = distance(center, a);
  64.     return Circle(center, radius);
  65. }
  66.  
  67. // 计算两点构成的圆
  68. Circle circleFrom2Points(const Point& a, const Point& b) {
  69.     Point center((a.x + b.x)/2, (a.y + b.y)/2);
  70.     double radius = distance(a, b) / 2;
  71.     return Circle(center, radius);
  72. }
  73.  
  74. // 检查圆是否包含所有点
  75. bool isValidCircle(const Circle& c, const vector<Point>& points) {
  76.     for (const auto& p : points) {
  77.         if (!c.contains(p)) {
  78.             return false;
  79.         }
  80.     }
  81.     return true;
  82. }
  83.  
  84. // 计算一组点的最小外切圆（使用朴素算法，适合小规模数据）
  85. Circle minEnclosingCircle(const vector<Point>& points) {
  86.     int n = points.size();
  87.  
  88.     if (n == 0) {
  89.         return Circle(Point(0, 0), 0);
  90.     } else if (n == 1) {
  91.         return Circle(points[0], 0);
  92.     }
  93.  
  94.     Circle minCircle(Point(0, 0), 1e18);
  95.  
  96.     // 尝试所有两点组合作为直径
  97.     for (int i = 0; i < n; i++) {
  98.         for (int j = i+1; j < n; j++) {
  99.             Circle c = circleFrom2Points(points[i], points[j]);
  100.             if (isValidCircle(c, points) && c.radius < minCircle.radius) {
  101.                 minCircle = c;
  102.             }
  103.         }
  104.     }
  105.  
  106.     // 尝试所有三点组合作为外接圆
  107.     for (int i = 0; i < n; i++) {
  108.         for (int j = i+1; j < n; j++) {
  109.             for (int k = j+1; k < n; k++) {
  110.                 Circle c = circleFrom3Points(points[i], points[j], points[k]);
  111.                 if (isValidCircle(c, points) && c.radius < minCircle.radius) {
  112.                     minCircle = c;
  113.                 }
  114.             }
  115.         }
  116.     }
  117.  
  118.     return minCircle;
  119. }
  120.  
  121. int main() {
  122.     int m;
  123.     cin >> m;
  124.  
  125.     vector<int> groupSizes(m);
  126.     int totalPoints = 0;
  127.  
  128.     // 读取每组点的数量
  129.     for (int i = 0; i < m; i++) {
  130.         cin >> groupSizes[i];
  131.         totalPoints += groupSizes[i];
  132.     }
  133.  
  134.     // 读取所有点
  135.     vector<Point> allPoints(totalPoints);
  136.     for (int i = 0; i < totalPoints; i++) {
  137.         cin >> allPoints[i].x >> allPoints[i].y;
  138.     }
  139.  
  140.     // 读取待判定点
  141.     Point target;
  142.     cin >> target.x >> target.y;
  143.  
  144.     // 处理每组点
  145.     vector<int> resultGroups;
  146.     int pointIndex = 0;
  147.  
  148.     for (int groupId = 0; groupId < m; groupId++) {
  149.         // 提取当前组的点
  150.         vector<Point> groupPoints;
  151.         for (int j = 0; j < groupSizes[groupId]; j++) {
  152.             groupPoints.push_back(allPoints[pointIndex++]);
  153.         }
  154.  
  155.         // 计算当前组的最小外切圆
  156.         Circle minCircle = minEnclosingCircle(groupPoints);
  157.  
  158.         // 检查目标点是否在圆内
  159.         if (minCircle.contains(target)) {
  160.             resultGroups.push_back(groupId);
  161.         }
  162.     }
  163.  
  164.     // 输出结果
  165.     if (resultGroups.empty()) {
  166.         cout << "null" << endl;
  167.     } else {
  168.         for (size_t i = 0; i < resultGroups.size(); i++) {
  169.             if (i > 0) cout << " ";
  170.             cout << resultGroups[i];
  171.         }
  172.         cout << endl;
  173.     }
  174.  
  175.     return 0;
  176. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
2
2 4
0 0
1 1
2 2 
2 3
3 2
3 4
3 3
stdout
copy 
1
https://ideone.com/Qm8r6x
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!