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

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

推荐阅读

go
USACO 2014 Jan - Moolympics区间记录优化算法

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

蜡笔小新 2024-12-27 18:14:31
go
词根词缀解析：greg、hap、helio及其他词源故事

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

蜡笔小新 2024-12-27 18:59:50
java
深入理解org.neo4j.helpers.collection.Iterators.single()方法及其应用

本文详细介绍了Java中org.neo4j.helpers.collection.Iterators.single()方法的功能、使用场景及代码示例，帮助开发者更好地理解和应用该方法。 ... [详细]

蜡笔小新 2024-12-28 10:51:55
java
优化ListView性能

本文深入探讨了如何通过多种技术手段优化ListView的性能，包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]

蜡笔小新 2024-12-28 10:36:30
go
编写有趣的VBScript恶作剧脚本

本文将介绍如何编写一些有趣的VBScript脚本，这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例，帮助您了解VBScript的基本语法和功能。 ... [详细]

蜡笔小新 2024-12-28 09:46:23
perl
网络链路质量监控：Smokeping部署与配置

本文详细介绍了如何在Linux系统上安装和配置Smokeping，以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装，确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]

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

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

蜡笔小新 2024-12-28 11:30:01
get
深入解析Android自定义View面试题

本文探讨了Android Launcher开发中自定义View的重要性，并通过一道经典的面试题，帮助开发者更好地理解自定义View的实现细节。文章不仅涵盖了基础知识，还提供了实际操作建议。 ... [详细]

蜡笔小新 2024-12-28 11:15:04
java
GWT PopupPanel onKeyDownPreview 方法详解与实例

本文详细介绍了 GWT 中 PopupPanel 类的 onKeyDownPreview 方法，提供了多个代码示例及应用场景，帮助开发者更好地理解和使用该方法。 ... [详细]

蜡笔小新 2024-12-28 10:07:27
java
Handling Null Object Encoding in OAuth 1.0a API Implementation

Explore a common issue encountered when implementing an OAuth 1.0a API, specifically the inability to encode null objects and how to resolve it. ... [详细]

蜡笔小新 2024-12-28 08:54:34
get
Python配置文件读写指南

本文详细介绍如何使用Python进行配置文件的读写操作，涵盖常见的配置文件格式（如INI、JSON、TOML和YAML），并提供具体的代码示例。 ... [详细]

蜡笔小新 2024-12-28 08:39:55
select
技术分享：从动态网站提取站点密钥的解决方案

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

蜡笔小新 2024-12-28 04:11:47
go
Installing the MongoDB PHP Driver on XAMPP for macOS

This guide provides a comprehensive step-by-step approach to successfully installing the MongoDB PHP driver on XAMPP for macOS, ensuring a smooth and efficient setup process. ... [详细]

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

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

蜡笔小新 2024-12-27 18:36:54
go
数据管理权威指南：《DAMA-DMBOK2 数据管理知识体系》

本书提供了全面的数据管理职能、术语和最佳实践方法的标准行业解释，构建了数据管理的总体框架，为数据管理的发展奠定了坚实的理论基础。适合各类数据管理专业人士和相关领域的从业人员。 ... [详细]

蜡笔小新 2024-12-27 18:29:55

小美女爆米花

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

Tags | 热门标签

RankList | 热门文章