csu 1011 Counting Pixels

想像していなかった複雑さ.
まず園を4つに分けて計算量を減らす(さらに8つに細分化することもでき、やや複雑である).
円がどのように1つの画素を通過するかを判断します:右上の点に対して、3つの情況しかありません:右から通り抜けて、右下の頂点から通り抜けて、下から通り抜けます;
最初の画素(通過)が与えられ、その後、通過した場合に応じて次の通過した画素が拡張され、状況に応じてカウントされる.
ピクセルの表示:右上のポイントの座標:     Language: C      Result: Accepted      Time:236 ms      Memory:740 kb
最も速いのは128 msだけで、指摘を求めます.

 1 # include <stdio.h>
 2  
 3  int x, y, r;
 4  
 5  int state(int x, int y);   // 1: right, 0: corner, -1: bottom
 6  
 7  int main()
 8  {
 9      long long cnt;
10     
11      freopen("in.txt", "r", stdin);
12      freopen("out.txt", "w", stdout);
13      
14      while (~scanf("%d%d%d", &x, &y, &r))
15      {
16            if (!(x || y || r)) break;
17            cnt = 0;
18            x = 1, y = r; 
19            while (x <= r && y >= 1)
20            {
21                if (state(x, y) == 1) ++cnt, --y;
22                else if (state(x, y) == 0) cnt += y, ++x, --y;
23                else if (state(x, y) == -1) cnt += y, ++x;
24                else printf("wrong
");
25            }
26            printf("%lld
", cnt<<2);
27      }
28      
29      return 0;    
30  }
31  
32  int state(int x, int y)
33  {
34      int t1, t2;
35      --y;
36      t2 = r*r;
37      t1 = x*x + y*y;
38      if (t1 > t2) return 1; 
39      if (t1 == t2) return 0;
40      if (t1 < t2) return -1;
41  }

2012/3/13  00:10
上記コードの19行目のループでは、一時変数tmpを設定し、state(x,y)の値を保存し、消費時間(200 ms)を低減することができる.