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