暑假强化训练：计算几何深度探索

作者：小美女爆米花 | 来源：互联网 | 2024-11-08 16:20

经过两天的努力，终于成功解决了半平面交模板题POJ3335的问题。原来是在`OnLeft`函数中漏掉了关键的等于号。通过这次训练，不仅加深了对半平面交算法的理解，还提升了调试和代码实现的能力。未来将继续深入研究计算几何的其他核心问题，进一步巩固和拓展相关知识。

交了两天的半平面交的模版题终于过了，，，原来是 OnLeft 里面少抄了一个等于号......

半平面交 poj3335

  1 #include 
  2 #include 
  3 #include 
  4 #include 
  5 #include 
  6 #include 
  7 #include 
  8 #include 
  9 #include <string>
 10 #include 
 11 #include 
 12 #include 
 13 #include <set>
 14 #define LL long long
 15 #define INF 0x3f3f3f3f
 16 #define eps 1e-10
 17 #define OPEN_FILE
 18 using namespace std;
 19 int n;
 20 
 21 int dcmp(double x){
 22     if (fabs(x) return 0;
 23     return x <0 ? -1 : 1;
 24 }
 25 struct Point{
 26     double x, y;
 27     Point(double p = 0, double q = 0){
 28         x = p;
 29         y = q;
 30     }
 31 };
 32 struct Node{
 33     int p;
 34     Point A, B;
 35     Node(Point a1, Point a2, int t){
 36         A = a1;
 37         B = a2;
 38         p = t;
 39     }
 40 };
 41 typedef Point Vector;
 42 
 43 Vector operator + (Vector A, Vector B){
 44     return Vector(A.x + B.x, A.y + B.y);
 45 }
 46 Vector operator - (Vector A, Vector B){
 47     return Vector(A.x - B.x, A.y - B.y);
 48 }
 49 Vector operator * (Vector A, double p){
 50     return Vector(A.x * p, A.y * p);
 51 }
 52 Vector operator / (Vector A, double p){
 53     return Vector(A.x / p, A.y / p);
 54 }
 55 bool operator == (Vector A, Vector B){
 56     return dcmp(A.x - B.x) == 0 && dcmp(A.y - B.y) == 0;
 57 }
 58 bool operator > (Vector A, Vector B){
 59     return A.x > B.x && A.y > B.y;
 60 }
 61 bool operator <(Vector A, Vector B){
 62     return A.x  B.y;
 63 }
 64 //点积
 65 double  Dot(Vector A, Vector B){
 66     return A.x * B.x + A.y * B.y;
 67 }
 68 //模
 69 double Length(Vector A){
 70     return sqrt(Dot(A, A));
 71 }
 72 //夹角
 73 double Angle(Vector A, Vector B){
 74     return acos(Dot(A, B) / Length(A) / Length(B));
 75 }
 76 //叉积
 77 double Cross(Vector A, Vector B){
 78     return A.x * B.y - A.y*B.x;
 79 }
 80 //三角形面积
 81 double Area2(Point A, Point B, Point C){
 82     return Cross(B - A, C - A);
 83 }
 84 struct Line
 85 {
 86     Point p;
 87     Vector v;
 88     double angle;
 89     Line(){}
 90     Line(Point p, Vector v) :p(p), v(v){
 91         angle = atan2(v.y, v.x);
 92     }
 93     bool operator <(const Line & L) const{
 94         return angle<L.angle;
 95     }
 96 };
 97 //点p在直线L的左边
 98 bool OnLeft(Line L, Point p) { return Cross(L.v, p - L.p)>=0; }
 99 //直线A，B的交点
100 Point GetIntersection(Line A, Line B)
101 {
102     Vector u = A.p - B.p;
103     double t = Cross(B.v, u) / Cross(A.v, B.v);
104     return A.p + A.v*t;
105 }
106 
107 int HalfplaneIntersection(Line *L, int n, Point *poly)
108 {
109     sort(L, L + n);
110 
111     int first, last;
112     Point *p = new Point[n];
113     Line *q = new Line[n];
114     q[first = last = 0] = L[0];
115     for (int i = 1; i )
116     {
117         while (first 1])) last--;
118         while (first ;
119         q[++last] = L[i];
120         if (fabs(Cross(q[last].v, q[last - 1].v)) < eps)
121         {
122             last--;
123             if (OnLeft(q[last], L[i].p)) q[last] = L[i];
124         }
125         if (first 1] = GetIntersection(q[last - 1], q[last]);
126     }
127     while (first 1])) last--;
128     if (last - first <= 1) return 0;
129     p[last] = GetIntersection(q[last], q[first]);
130     int m = 0;
131     for (int i = first; i <= last; i++) poly[m++] = p[i];
132     return m;
133 }
134 
135 Line L[105];
136 Point P[105], poly[105];
137 Vector v[105];
138 int main()
139 {
140 #ifdef OPEN_FILE
141     //freopen("in.txt", "r", stdin);
142     //freopen("out.txt", "w", stdout);
143 #endif // OPEN_FILE
144     int T;
145     scanf("%d", &T);
146     double x, y;
147     for (int cas = 1; cas <= T; cas++){
148         scanf("%d", &n);
149         for (int i = 0; i )
150         {
151             scanf("%lf%lf", &x, &y);
152             P[i] = Point(x, y);
153         }
154         for (int i = 0; i ){
155             v[i] = P[i] - P[(i + 1) % n];
156         }
157         for (int i = 0; i )
158         {
159             L[i] = Line(P[i], v[i]);
160         }
161         if (HalfplaneIntersection(L, n, poly) != 0){
162             printf("YES\n");
163         }
164         else{
165             printf("NO\n");
166         }
167     }
168 }

View Code

凸包加旋转卡壳 poj2187

  1 #include 
  2 #include 
  3 #include 
  4 #include 
  5 #include 
  6 #include 
  7 #include 
  8 #include 
  9 #include <string>
 10 #include 
 11 #include 
 12 #include 
 13 #include <set>
 14 #define LL long long
 15 #define INF 0x3f3f3f3f
 16 #define OPEN_FILE
 17 using namespace std;
 18 
 19 #define eps 1e-8
 20 
 21 struct Point{
 22     int x, y;
 23     Point(int p = 0, int q = 0){
 24         x = p;
 25         y = q;
 26     }
 27 };
 28 typedef Point Vector;
 29 
 30 Vector operator + (Vector A, Vector B){
 31     return Vector(A.x + B.x, A.y + B.y);
 32 }
 33 Vector operator - (Vector A, Vector B){
 34     return Vector(A.x - B.x, A.y - B.y);
 35 }
 36 Vector operator * (Vector A, int p){
 37     return Vector(A.x * p, A.y * p);
 38 }
 39 Vector operator / (Vector A, int p){
 40     return Vector(A.x / p, A.y / p);
 41 }
 42 bool operator == (Vector A, Vector B){
 43     return A.x - B.x == 0 && A.y - B.y == 0;
 44 }
 45 bool operator > (Vector A, Vector B){
 46     return A.x > B.x ||(A.x == B.x && A.y > B.y);
 47 }
 48 bool operator <(Vector A, Vector B){
 49     return A.x  B.y);
 50 }
 51 
 52 int Cross(Vector A, Vector B){
 53     return A.x * B.y - A.y*B.x;
 54 }
 55 int Distance(Point a, Point b){
 56     return  (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
 57 }
 58 int ConvexHull(Point *p, int n, Point* ch){
 59     sort(p, p + n);
 60     int m = 0;
 61     for (int i = 0; i ){
 62         while (m > 1 && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0){
 63             m--;
 64         }
 65         ch[m++] = p[i];
 66     }
 67     int k = m;
 68     for (int i = n - 2; i >= 0; i--){
 69         while (m > k && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0){
 70             m--;
 71         }
 72         ch[m++] = p[i];
 73     }
 74     if (n > 1){
 75         m--;
 76     }
 77     return m;
 78 }
 79 int RotateCaliper(int m, Point *ch){
 80     if (m == 2) return Distance(ch[0], ch[1]);
 81 
 82     int i, j;
 83     i = j = 0;
 84     for (int k = 0; k){
 85         if (ch[i].x>ch[k].x){
 86             i = k;
 87         }
 88         if (ch[j].x < ch[k].x){
 89             j = k;
 90         }
 91     }
 92     int res = 0, si = i, sj = j;
 93 
 94     while (i != sj || j != si)
 95     {
 96         res = max(res, Distance(ch[i], ch[j]));
 97         if (Cross(ch[(i + 1) % m] - ch[i], ch[(j + 1) % m] - ch[j]) <0){
 98             i = (i + 1) % m;
 99         }
100         else {
101             j = (j + 1) % m;
102         }
103     }
104     return  res;
105 }
106 const int MAXN = 50005;
107 int n;
108 Point p[MAXN], ch[MAXN];
109 int main()
110 {
111 #ifdef OPEN_FILE
112     //freopen("in.txt", "r", stdin);
113     //freopen("out.txt", "w", stdout);
114 #endif // OPEN_FILE
115     while (~scanf("%d", &n)){
116         for (int i = 0; i ){
117             scanf("%d%d", &p[i].x, &p[i].y);
118         }
119         int m = ConvexHull(p, n, ch);    
120         int ans = RotateCaliper(m, ch);
121         printf("%d\n", ans);
122     }
123 }

View Code

推荐阅读

char
洛谷 P1344 坏牛奶追踪问题（最小割算法应用）

在洛谷 P1344 的坏牛奶追踪问题中，第一问要求计算最小割，而第二问则需要找到割边数量最少的最小割。通过为每条边附加一个单位权值，可以在求解最小割时优先选择边数较少的方案，从而同时解决两个问题。这种策略不仅简化了问题的求解过程，还确保了结果的最优性。 ... [详细]

蜡笔小新 2024-11-07 14:50:22
int
Kuangbin 数学训练营：Ekka Dokka 深度解析与应用

本文深入解析了 Kuangbin 数学训练营中的经典问题——Ekka Dokka，并通过详细的代码示例和数学推导，探讨了该问题的多种解法及其应用场景。通过对算法的优化和扩展，本文旨在为读者提供全面的理解和实用的参考。 ... [详细]

蜡笔小新 2024-11-08 16:39:26
int
洛谷 P4035 [JSOI2008] 球形空间生成器（高斯消元法 / 模拟退火算法）

本文介绍了洛谷 P4035 [JSOI2008] 球形空间生成器问题的解决方案，主要使用了高斯消元法和模拟退火算法。通过这两种方法，可以高效地求解多维空间中的球心位置。文章提供了详细的算法模板和实现代码，适用于 ACM 竞赛和其他相关应用场景。数据范围限制在 10 以内，确保了算法的高效性和准确性。 ... [详细]

蜡笔小新 2024-11-08 13:55:00
text
Vue 页面状态管理与跨页面数据传递的有效策略

在 Vue 应用开发中，页面状态管理和跨页面数据传递是常见需求。本文将详细介绍 Vue Router 提供的两种有效方式，帮助开发者高效地实现页面间的数据交互与状态同步，同时分享一些最佳实践和注意事项。 ... [详细]

蜡笔小新 2024-11-08 12:45:14
int
佩尔方程的递推关系式：x² - dy² = 1 的深入解析

本文深入探讨了佩尔方程 \( x^2 - dy^2 = 1 \) 的递推关系式。通过构造特定的矩阵并利用矩阵快速幂的方法，可以高效地计算出该方程的第 k 组解。此外，文章还详细分析了递推关系式的数学背景及其在数论中的应用，为相关研究提供了坚实的理论基础。 ... [详细]

蜡笔小新 2024-11-08 11:28:27
char
在Django中提交表单时遇到值错误问题如何解决？

在Django项目中，当用户提交包含多个选择目标的表单时，可能会遇到值错误问题。本文将探讨如何通过优化表单处理逻辑和验证机制来有效解决这一问题，确保表单数据的准确性和完整性。 ... [详细]

蜡笔小新 2024-11-08 10:29:57
format
C++ 开发实战：实用技巧与经验分享

C++ 开发实战：实用技巧与经验分享 ... [详细]

蜡笔小新 2024-11-07 20:31:03
char
单链表的高效遍历及性能优化策略

本文探讨了单链表的高效遍历方法及其性能优化策略。在单链表的数据结构中，插入操作的时间复杂度为O(n)，而遍历操作的时间复杂度为O(n^2)。通过在 `LinkList.h` 和 `main.cpp` 文件中对单链表进行封装，我们实现了创建和销毁功能的优化，提高了单链表的使用效率。此外，文章还介绍了几种常见的优化技术，如缓存节点指针和批量处理，以进一步提升遍历性能。 ... [详细]

蜡笔小新 2024-11-07 15:55:20
char
在Kohana 3中实现最优的“即时消息”显示方法 - Best Practices for Displaying 'Flash Messages' in Kohana 3

在Kohana 3框架中，实现最优的即时消息显示方法是许多开发者关注的问题。本文将探讨如何高效、优雅地展示flash消息，包括最佳实践和技术细节，以提升用户体验和代码可维护性。 ... [详细]

蜡笔小新 2024-11-06 21:13:53
char
利用GLSL在iOS上实现YV12到RGB的转换，并附带展示结果图像

本文介绍了如何在iOS平台上使用GLSL着色器将YV12格式的视频帧数据转换为RGB格式，并展示了转换后的图像效果。通过详细的技术实现步骤和代码示例，读者可以轻松掌握这一过程，适用于需要进行视频处理的应用开发。 ... [详细]

蜡笔小新 2024-11-06 19:18:22
char
寒假作业解析：第三周 2月12日第7题

尽快完成之前的练习任务！每日一练2.1 Problem A Laurenty and Shop 的题目要求是选择两条不同的路线以最小化总的等待时间。简要分析：通过对比不同路线的等待时间，可以找到最优解。此问题可以通过动态规划或贪心算法来解决，具体取决于路线的复杂性和约束条件。 ... [详细]

蜡笔小新 2024-11-06 14:33:36
text
Spring框架的核心组件与架构解析

Spring框架的核心组件与架构解析 ... [详细]

蜡笔小新 2024-11-06 14:16:03
int
蓝桥杯算法实战：节点选取策略优化分析

本文针对蓝桥杯算法竞赛中的节点选取策略进行了深入分析与优化。通过对比不同节点选择方法的效果，提出了基于贪心算法和动态规划的综合优化方案，旨在提高算法效率和准确性。实验结果表明，该优化策略在处理大规模数据集时表现出色，显著提升了算法性能。 ... [详细]

蜡笔小新 2024-11-06 12:51:58
future
投融资周报 | Circle 达成 4 亿美元融资协议，唯一艺术平台 A 轮融资超千万美元

投融资周报 | Circle 达成 4 亿美元融资协议，唯一艺术平台 A 轮融资超千万美元 ... [详细]

蜡笔小新 2024-11-05 04:56:42
text
利用Dom4j和JFileChooser在Java中实现XML文件的自定义路径导出功能

本文介绍了一种利用Dom4j库和JFileChooser组件在Java中实现XML文件自定义路径导出的方法。通过创建一个Document对象并设置根元素，结合JFileChooser选择目标路径，实现了灵活的XML文件导出功能。具体步骤包括初始化Document对象、构建XML结构以及使用JFileChooser选择保存路径，确保用户能够方便地将生成的XML文件保存到指定位置。 ... [详细]

蜡笔小新 2024-11-05 09:06:03

小美女爆米花

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章