前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >算法模板——计算几何1(图形面积)

算法模板——计算几何1(图形面积)

作者头像
HansBug
发布于 2018-04-10 08:36:50
发布于 2018-04-10 08:36:50
70100
代码可运行
举报
文章被收录于专栏:HansBug's LabHansBug's Lab
运行总次数:0
代码可运行

实现功能——输入N个点,求出按此顺序围成的图形的面积

原理:其实就是个向量的叉积运算(详见UASCO-nocow:计算几何),注意二维的叉积是个很逗的东西,叉积这玩意本身就来自于三维向量

(HansBug:临睡觉了,水一发呵呵哒,额。。。phile犇不在好寂寞TT)

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
 1 var
 2    i,j,k,l,m,n:longint;
 3    a:array[0..100000,1..2] of longint;
 4 function surface:extended;inline;
 5          var
 6             i,j:longint;
 7          begin
 8               j:=0;
 9               for i:=1 to n do
10                   j:=j+(a[i,1]*a[(i mod n)+1,2])-(a[(i mod n)+1,1]*a[i,2]);
11               exit(abs(j)/2);
12          end;
13 begin
14      readln(n);
15      for i:=1 to n do readln(a[i,1],a[i,2]);
16      writeln(surface:0:2);
17      readln;
18 end.
19               
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2015-01-20 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
1051: [HAOI2006]受欢迎的牛
1051: [HAOI2006]受欢迎的牛 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 2410  Solved: 1276 [Submit][Status] Description 每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛,给你M对整数(A,B),表示牛A认为牛B受欢迎。 这种关系是具有传递性的,如果A认为B受欢迎,B认为C受欢迎,那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。 Input 第一行两个数N,M。
HansBug
2018/04/10
6070
算法模板——线性筛素数
实现功能:如题,筛出1——N内的所有素数 原理:如phile神犇所言,这次的才算是真正意义上的线性筛素数,其精髓在于if (i mod a[j])=0 then break; 因为——如果眼下的a[j]已经是i的因数了,则意味着即使再进行b[i*a[j]]:=1,那么I*b[j]也必然会被其他的数以同样的操作覆盖到,所以可以退出了,这个算法的思想在于减少重复劳动(鸣谢qcgrxx神犇,源链接) 1 var 2 i,j,k,l,m,n:longint; 3 a,b:array[0..1000
HansBug
2018/04/11
5710
3314: [Usaco2013 Nov]Crowded Cows
3314: [Usaco2013 Nov]Crowded Cows Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 111  Solved: 79 [Submit][Status][Discuss] Description  Farmer John's N cows (1 <= N <= 50,000) are grazing along a one-dimensional fence. Cow i is standing at location x(i) a
HansBug
2018/04/11
5970
1635: [Usaco2007 Jan]Tallest Cow 最高的牛
1635: [Usaco2007 Jan]Tallest Cow 最高的牛 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 383  Solved: 211 [Submit][Status] Description FJ's N (1 <= N <= 10,000) cows conveniently indexed 1..N are standing in a line. Each cow has a positive integer height (whic
HansBug
2018/04/10
7740
3224: Tyvj 1728 普通平衡树
3224: Tyvj 1728 普通平衡树 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 2566  Solved: 1031 [Submit][Status] Description 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作: 1. 插入x数 2. 删除x数(若有多个相同的数,因只删除一个) 3. 查询x数的排名(若有多个相同的数,因输出最小的排名) 4. 查询排名为x的数 5. 求x的前驱(前驱定义为小于x,且最大的数
HansBug
2018/04/10
7060
1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场
1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 498  Solved: 223 [Submit][Status] Description The farm has many hills upon which Farmer John would like to place guards to ensure the safety of his valuable milk-cow
HansBug
2018/04/10
5600
1644: [Usaco2007 Oct]Obstacle Course 障碍训练课
1644: [Usaco2007 Oct]Obstacle Course 障碍训练课 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 383  Solved: 196 [Submit][Status][Discuss] Description 考虑一个 N x N (1 <= N <= 100)的有1个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的,它们被标记为了'x'。例如下图: . . B x . . x x A . . . . x . . x . .
HansBug
2018/04/11
7340
算法模板——计算几何2(二维凸包——Andrew算法)
实现功能:求出二维平面内一对散点的凸包(详见Codevs 1298) 很神奇的算法——先将各个点按坐标排序,然后像我们所知的那样一路左转,求出半边的凸包,然后反过来求另一半的凸包 我以前正是因为总抱着想一步到位的想法,所以每次都跪得很惨(HansBug:事实上这次是我这辈子第一次A掉凸包题) 然后别的没了,就是凸包的基本思想 (顺便输出凸包周长C和面积S) 1 type arr=array[0..100005] of longint; 2 var 3 i,j,k,l,m,n,m1,m2:long
HansBug
2018/04/11
5680
2751: [HAOI2012]容易题(easy)
2751: [HAOI2012]容易题(easy) Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 1087  Solved: 477 [Submit][Status][Discuss] Description 为了使得大家高兴,小Q特意出个自认为的简单题(easy)来满足大家,这道简单题是描述如下: 有一个数列A已知对于所有的A[i]都是1~n的自然数,并且知道对于一些A[i]不能取哪些值,我们定义一个数列的积为该数列所有元素的乘积,要求你求出所有可能的
HansBug
2018/04/11
5140
1611: [Usaco2008 Feb]Meteor Shower流星雨
1611: [Usaco2008 Feb]Meteor Shower流星雨 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 1010  Solved: 446 [Submit][Status][Discuss] Description 去年偶们湖南遭受N年不遇到冰冻灾害,现在芙蓉哥哥则听说另一个骇人听闻的消息: 一场流星雨即将袭击整个霸中,由于流星体积过大,它们无法在撞击到地面前燃烧殆尽, 届时将会对它撞到的一切东西造成毁灭性的打击。很自然地,芙蓉哥哥开始担心自
HansBug
2018/04/10
6240
从Hash Killer I、II、III论字符串哈希
首先,Hash Killer I、II、III是BZOJ上面三道很经典的字符串哈希破解题。当时关于II,本人还琢磨了好久,但一直不明白为啥别人AC的代码都才0.3kb左右,直到CYG神犇说可以直接随机水过去,遂恍然大悟。。。 于是,本人今天也做了下实验——假设现在有一个字符串题:输入N,接下来N行输入N个长度一样的由大写字母组成的字符串,求一共有多少种不同的字符串。此题有些类似于Hash Killer上面的原题。首先分析此题本身,两种常规办法:1.建立一棵字典树,然后可以相当方便快捷的判重,对于字符串长度均
HansBug
2018/04/10
9630
3407: [Usaco2009 Oct]Bessie's Weight Problem 贝茜的体重问题
3407: [Usaco2009 Oct]Bessie's Weight Problem 贝茜的体重问题 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: 48  Solved: 46 [Submit][Status][Discuss] Description     贝茜像她的诸多姊妹一样,因为从约翰的草地吃了太多美味的草而长出了太多的赘肉.所以约翰将她置于一个及其严格的节食计划之中.她每天不能吃多过H(5≤日≤45000)公斤的干草.贝茜只能吃一整捆干草;
HansBug
2018/04/11
6050
3404: [Usaco2009 Open]Cow Digit Game又见数字游戏
3404: [Usaco2009 Open]Cow Digit Game又见数字游戏 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: 72  Solved: 48 [Submit][Status][Discuss] Description     贝茜和约翰在玩一个数字游戏.贝茜需要你帮助她.     游戏一共进行了G(1≤G≤100)场.第i场游戏开始于一个正整数Ni(l≤Ni≤1,000,000).游 戏规则是这样的:双方轮流操作,将当前的数字减去一个数,
HansBug
2018/04/11
7760
算法模板——Dinic最小费用最大流
实现功能:输入M,N,S,T;接下来M行输入M条弧的信息(包括起点,终点,流量,单位费用);实现功能是求出以S为源点,T为汇点的网络最大流的最小费用 其实相当的像Dinic最大流呐= = 还是spfa处理出最短路径(注意,这次是最短路径,所以时空复杂度将有所提高,害得我都开循环队列了TT),然后顺着最短路径顺藤摸瓜找回去,求出流大小和最小的费用,然后,没有然后了,程序还是一样的好懂么么哒(HansBug:感觉Dinic算法真心超级喜感,为啥我之前就没发现呢= =,还有鸣谢wnjxyk神犇提供的C++模板么么
HansBug
2018/04/11
2.4K0
1297: [SCOI2009]迷路
1297: [SCOI2009]迷路 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 652  Solved: 442 [Submit][Status] Description windy在有向图中迷路了。 该有向图有 N 个节点,windy从节点 0 出发,他必须恰好在 T 时刻到达节点 N-1。 现在给出该有向图,你能告诉windy总共有多少种不同的路径吗? 注意:windy不能在某个节点逗留,且通过某有向边的时间严格为给定的时间。 Input 第一行包
HansBug
2018/04/10
5300
2292: 【POJ Challenge 】永远挑战
2292: 【POJ Challenge 】永远挑战 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 553  Solved: 230 [Submit][Status][Discuss] Description lqp18_31和1tthinking经常出题来虐ftiasch。有一天, lqp18_31搞了一个有向图,每条边的长度都是1。 他想让ftiasch求出点1到点 N 的最短路。"水题啊。", ftiasch这么说道。 所以1tthinking把某些
HansBug
2018/04/11
5710
2292: 【POJ Challenge 】永远挑战
3384/1750: [Usaco2004 Nov]Apple Catching 接苹果
3384/1750: [Usaco2004 Nov]Apple Catching 接苹果 Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 18  Solved: 16 [Submit][Status][Discuss] Description     很少有人知道奶牛爱吃苹果.农夫约翰的农场上有两棵苹果树(编号为1和2),每一棵树上都长满了苹果.奶牛贝茜无法摘下树上的苹果,所以她只能等待苹果从树上落下.但是,由于苹果掉到地上会摔烂,贝茜必须在半空中接住苹果(
HansBug
2018/04/11
7240
1708: [Usaco2007 Oct]Money奶牛的硬币
1708: [Usaco2007 Oct]Money奶牛的硬币 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 544  Solved: 352 [Submit][Status] Description 在创立了她们自己的政权之后,奶牛们决定推广新的货币系统。在强烈的叛逆心理的驱使下,她们准备使用奇怪的面值。在传统的货币系统中,硬币的面值通常是1,5,10,20或25,50,以及100单位的货币,有时为了更方便地交易,会发行面值为2单位的硬币。 奶牛们想知道,对
HansBug
2018/04/10
5340
算法模板——并查集 1
实现功能——操作1:将两个数字合并到一个集合内;操作2:判断两个数字是否在一起 第6行是亮点,这个优化能快出不少,真的 1 var 2 i,j,k,l,m,n:longint; 3 c:array[0..100000] of longint; 4 function getfat(x:longint):longint;inline; 5 begin 6 if c[x]<>x then c[x]:=getfat(c[x]); //亮点在这
HansBug
2018/04/10
5220
2764: [JLOI2011]基因补全
2764: [JLOI2011]基因补全 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 570  Solved: 187 [Submit][Status][Discuss] Description 在生物课中我们学过,碱基组成了DNA(脱氧核糖核酸),他们分别可以用大写字母A,C,T,G表示,其中A总与T配对,C总与G配对。两个碱基序列能相互匹配,当且仅当它们等长,并且任意相同位置的碱基都是能相互配对的。例如ACGTC能且仅能与TGCAG配对。一个相对短
HansBug
2018/04/11
9940
2764: [JLOI2011]基因补全
相关推荐
1051: [HAOI2006]受欢迎的牛
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验