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

作者：小美女爆米花 | 来源：互联网 | 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

推荐阅读

tree
Weight the Tree（树形dp）

题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅！－－－－－&# ... [详细]

蜡笔小新 2024-12-26 15:55:56
const
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新 2024-12-27 18:14:31
char
深入理解KMP算法中的next数组：北大OJ 2406题解

本文详细探讨了KMP算法中next数组的构建及其应用，重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现，帮助读者更好地理解KMP算法的核心原理。 ... [详细]

蜡笔小新 2024-12-28 11:30:01
int
古代密码变换问题

本题探讨了一种字符串变换方法，旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量，从而确定转换的可能性。 ... [详细]

蜡笔小新 2024-12-28 09:18:22
int
词根词缀解析：greg、hap、helio及其他词源故事

本文基于刘洪波老师的《英文词根词缀精讲》，深入探讨了多个重要词根词缀的起源及其相关词汇，帮助读者更好地理解和记忆英语单词。 ... [详细]

蜡笔小新 2024-12-27 18:59:50
copy
Dockerfile 编写与 Docker 网络配置详解

本文详细介绍了 Dockerfile 的编写方法及其在网络配置中的应用，涵盖基础指令、镜像构建与发布流程，并深入探讨了 Docker 的默认网络、容器互联及自定义网络的实现。 ... [详细]

蜡笔小新 2024-12-27 17:31:41
int
移动 UI 设计基础：打造简洁高效的用户界面

本章将深入探讨移动 UI 设计的核心原则，帮助开发者构建简洁、高效且用户友好的界面。通过学习设计规则和用户体验优化技巧，您将能够创建出既美观又实用的移动应用。 ... [详细]

蜡笔小新 2024-12-27 08:43:40
int
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

蜡笔小新 2024-12-26 20:04:36
char
Splay Tree 区间操作优化

本文详细介绍了使用Splay Tree进行区间操作的实现方法，包括插入、删除、修改、翻转和求和等操作。通过这些操作，可以高效地处理动态序列问题，并且代码实现具有一定的挑战性，有助于编程能力的提升。 ... [详细]

蜡笔小新 2024-12-26 18:47:12
request
技术分享：从动态网站提取站点密钥的解决方案

本文探讨了如何从动态网站中提取站点密钥，特别是针对验证码（reCAPTCHA）的处理方法。通过结合Selenium和requests库，提供了详细的代码示例和优化建议。 ... [详细]

蜡笔小新 2024-12-28 04:11:47
tree
C++实现经典排序算法

本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出，帮助读者全面了解这些排序方法的特点。 ... [详细]

蜡笔小新 2024-12-27 19:25:14
import
Python 的 10 个开发技巧！太实用了

1.如何在运行状态查看源代码？查看函数的源代码，我们通常会使用IDE来完成。比如在PyCharm中，你可以Ctrl+鼠标点击进入函数的源代码。那如果没有IDE呢？当我们想使用一个函 ... [详细]

蜡笔小新 2024-12-27 18:36:54
import
寻找满足特定条件的整数N的最大和(a+b)

本文探讨了如何在给定整数N的情况下，找到两个不同的整数a和b，使得它们的和最大，并且满足特定的数学条件。 ... [详细]

蜡笔小新 2024-12-26 19:26:18
char
C++ 中的数组与动态数组初始化

本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度，而 vector 是一种可扩展的容器，允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景，并提供了代码示例以加深理解。 ... [详细]

蜡笔小新 2024-12-26 15:38:03
buffer
VxWorks中的双向链表与环形缓冲应用

本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法，通过具体示例代码加深理解。 ... [详细]

蜡笔小新 2024-12-26 13:26:16

小美女爆米花

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

Tags | 热门标签

RankList | 热门文章