博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU 3775 Chain Code ——(Pick定理)
阅读量:6238 次
发布时间:2019-06-22

本文共 927 字,大约阅读时间需要 3 分钟。

  Pick定理运用在整点围城的面积,有以下公式:S围 = S内(线内部的整点个数)+ S线(线上整点的个数)/2 - 1。在这题上,我们可以用叉乘计算S围,题意要求的答案应该是S内+S线。那么我们进行推导以后得到ans=S内+S线=(S线+S围)/2+1-->另外,S线即是字符串的长度,那么本题得以解决。

  代码如下:

1 #include 
2 #include
3 #include
4 using namespace std; 5 typedef long long ll; 6 const int N = 1000000 + 5; 7 8 char s[N]; 9 int dx[] = {
0,-1,-1,-1,0,1,1,1};10 int dy[] = {
1,1,0,-1,-1,-1,0,1};11 12 int main()13 {14 while(scanf("%s",s+1) == 1)15 {16 ll all = 0;17 ll x = 0, y = 0;18 for(int i=1;s[i];i++)19 {20 int val = s[i] - '0';21 ll xx = x + dx[val];22 ll yy = y + dy[val];23 all += x * yy - xx * y;24 x = xx, y = yy;25 }26 all = std::abs(all);27 printf("%I64d\n",(all+strlen(s+1))/2 + 1);28 }29 return 0;30 }

 

转载于:https://www.cnblogs.com/zzyDS/p/6077396.html

你可能感兴趣的文章
CSS:阴影/边框/背景
查看>>
PHP 超级全局变量
查看>>
SQL的优化
查看>>
CodeIgniter HMVC 扩展
查看>>
Mybatis-Plus使用全解
查看>>
XMind浏览视图,你必须会使用
查看>>
OSChina 周日乱弹 ——会爬墙的不仅仅是壁虎还有班主任
查看>>
OSChina 周日乱弹 —— 小云云生日快乐
查看>>
负载均衡原理与实践详解 第一篇
查看>>
前端那些事之框架封装基础篇
查看>>
mysqld服务器cpu/iowait瞬间出现峰值的问题
查看>>
tornado的CURD操作
查看>>
Lambda对方法和构造器的引用
查看>>
ABBYY FineReader 12PDF选项卡之保存模式
查看>>
Python如何自定义模块?Python基础教程,第十讲,自定义模块
查看>>
monkeysocks开发日志--TCP协议分析及架构规划
查看>>
svn备份、转移、安装到新服务器
查看>>
初识systemd-使用篇
查看>>
全球BGP路由表浏览
查看>>
Hibernate持久化技术实例讲解
查看>>