HDU 3775 Chain Code ——(Pick定理)

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

  代码如下:

 #include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long ll;
const int N = + ; char s[N];
int dx[] = {,-,-,-,,,,};
int dy[] = {,,,-,-,-,,}; int main()
{
while(scanf("%s",s+) == )
{
ll all = ;
ll x = , y = ;
for(int i=;s[i];i++)
{
int val = s[i] - '';
ll xx = x + dx[val];
ll yy = y + dy[val];
all += x * yy - xx * y;
x = xx, y = yy;
}
all = std::abs(all);
printf("%I64d\n",(all+strlen(s+))/ + );
}
return ;
}
上一篇:android CheckBox RadioButton 照片和文字的间距问题


下一篇:JQuery------$.getJSON()方法的使用