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

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

推荐阅读

struct
紫荆花之恋：动态树上的小精灵友谊问题

本题来自WC2014，题目编号为BZOJ3435、洛谷P3920和UOJ55。该问题描述了一棵不断生长的带权树及其节点上小精灵之间的友谊关系，要求实时计算每次新增节点后树上所有可能的朋友对数。 ... [详细]

蜡笔小新 2024-12-22 14:36:54
request
HTTP请求与响应机制详解

本文深入探讨了HTTP请求和响应对象的使用，详细介绍了如何通过响应对象向客户端发送数据、处理中文乱码问题以及常见的HTTP状态码。此外，还涵盖了文件下载、请求重定向、请求转发等高级功能。 ... [详细]

蜡笔小新 2024-12-23 20:40:08
request
最小路径覆盖与强连通分量的应用：国王的问题

本题探讨了在一个有向图中，如何根据特定规则将城市划分为若干个区域，使得每个区域内的城市之间能够相互到达，并且划分的区域数量最少。题目提供了时间限制和内存限制，要求在给定的城市和道路信息下，计算出最少需要划分的区域数量。 ... [详细]

蜡笔小新 2024-12-23 18:42:12
request
丽江客栈选择问题

本文介绍了一道经典的算法题，题目涉及在丽江河边的n家特色客栈中选择住宿方案。两位游客希望住在色调相同的两家客栈，并在晚上选择一家最低消费不超过p元的咖啡店小聚。我们将详细探讨如何计算满足条件的住宿方案总数。 ... [详细]

蜡笔小新 2024-12-22 20:15:25
request
JSOI2010 蔬菜庆典：树结构中的无限大权值问题

本文探讨了 JSOI2010 的蔬菜庆典问题，主要关注如何处理非根非叶子节点的无限大权值情况。通过分析根节点及其子树的特性，提出了有效的解决方案，并详细解释了算法的实现过程。 ... [详细]

蜡笔小新 2024-12-22 18:57:48
version
解决C# Windows Forms客户端连接SignalR服务器时出现的错误

在尝试使用C# Windows Forms客户端通过SignalR连接到ASP.NET服务器时，遇到了内部服务器错误（500）。本文将详细探讨问题的原因及解决方案。 ... [详细]

蜡笔小新 2024-12-21 16:55:52
function
实现页面自动加载更多内容功能：类微博和Pinterest的设计

在现代Web应用中，当用户滚动到页面底部时，自动加载更多内容的功能变得越来越普遍。这种无刷新加载技术不仅提升了用户体验，还优化了页面性能。本文将探讨如何实现这一功能，并介绍一些实际应用案例。 ... [详细]

蜡笔小新 2024-12-23 17:01:04
foreach
java8新特性学习笔记

使用lambda表达式排序Collections.sort(temp,(Stringa,Stringb)-{returnb.compareTo(a);});Collections ... [详细]

蜡笔小新 2024-12-23 14:41:31
foreach
C++ 中的链表实现与应用

本文介绍如何在 C++ 中使用链表结构存储和管理数据。通过具体示例，展示了静态链表的基本操作，包括节点的创建、链接及遍历。 ... [详细]

蜡笔小新 2024-12-23 14:22:40
version
Android 自定义绘图板应用

本文介绍如何使用 Android 的 Canvas 和 View 组件创建一个简单的绘图板应用程序，支持触摸绘画和保存图片功能。 ... [详细]

蜡笔小新 2024-12-23 10:12:53
web
VC++如何监控cpu fan 转速?

主板IO用W83627THG,用VC如何取得CPU温度,系统温度,CPU风扇转速,VBat的电压. ... [详细]

蜡笔小新 2024-12-22 13:48:42
function
字符串中特定字符的移除方法

本文介绍如何从字符串中移除大写、小写、特殊、数字和非数字字符，并提供了多种编程语言的实现示例。 ... [详细]

蜡笔小新 2024-12-22 00:08:06
foreach
深入解析ESFramework中的AgileTcp组件

本文详细介绍了ESFramework框架中AgileTcp组件的设计与实现。AgileTcp是ESFramework提供的ITcp接口的高效实现，旨在优化TCP通信的性能和结构清晰度。 ... [详细]

蜡笔小新 2024-12-21 13:56:06
function
解决编译BSP包时遇到的 'gets' 未声明错误

在编译BSP包过程中，遇到了一个与 'gets' 函数相关的编译错误。该问题通常发生在较新的编译环境中，由于 'gets' 函数已被弃用并视为安全漏洞。本文将详细介绍如何通过修改源代码和配置文件来解决这一问题。 ... [详细]

蜡笔小新 2024-12-21 11:21:05
version
Java 中的不可变集合与同步集合详解

本文将详细探讨 Java 中提供的不可变集合（如 `Collections.unmodifiableXXX`）和同步集合（如 `Collections.synchronizedXXX`）的实现原理及使用方法，帮助开发者更好地理解和应用这些工具。 ... [详细]

蜡笔小新 2024-12-20 15:34:31

小美女爆米花

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

Tags | 热门标签

RankList | 热门文章