首页 > 代码库 > 计算几何
计算几何
贾老师不知道是怎么道听途说地了解到并到处宣扬我做了50道+ 的计算几何题，，明明一道都没有做过的我表示非常无奈，，但是为了不让贾老师收 flag， 我决定要做50道计算几何以示尊敬。
【bzoj1007】[HNOI2008]水平可见直线
显而易见， 我们最后看见的一定是一个下凸壳， 所以类似凸包那样求一遍就可以了。 因为它直接给的就是斜率所以说极角排序什么的就都可以直接省掉了， 以k 为 第一关键字， b 为第二关键字排一遍然后用栈维护一下就可以了。 设当前要插入的直线为 k， 栈顶元素为 top， 栈顶元素前一位为 top - 1， 要将栈顶元素弹出当且仅当 top - 1 与 k 的交点 在 top 与 top - 1 的交点的 左边。
#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>#define MAXN 50005using namespace std;int n, stack[MAXN], top, ans[MAXN];struct point{double k, b; int num;} p[MAXN];bool cmp(point a, point b){if(a.k == b.k)return a.b < b.b; return a.k < b.k;}double jiao(point a, point b){return (b.b - a.b) / (a.k - b.k);}bool insert(point a, int i){ while(top){ if(a.k == p[stack[top]].k)top --; else if(top > 1 && jiao(a, p[stack[top - 1]]) <= jiao(p[stack[top - 1]], p[stack[top]])) top --; else break; } stack[++ top] = i; }int main(){ scanf("%d", &n); for(int i = 1; i <= n; i ++)scanf("%lf%lf", &p[i].k, &p[i].b), p[i].num = i; sort(p + 1, p + n + 1, cmp); for(int i = 1; i <= n; i ++)insert(p[i], i); for(int i = 1; i <= top; i ++)ans[p[stack[i]].num] = 1; for(int i = 1; i <= n; i ++)if(ans[i])printf("%d ", i); return 0;}
计算几何
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。