schindlerlee 2010-11-04 14:58 发表评论

schindlerlee 2010-10-26 12:41 发表评论

  1 /* 
  2  * SOUR:zju2589
  3  * ALGO:computational geomtry 计算平面上不重合的n个圆形成的区域
  4  * 基本的方法，如图所示，将所有圆之间的交点作为点，将在同一个圆上的所有交点之间的弧作
  5  * 为边建立一张有向图，之后可以利用平面图的欧拉定理
  6  *           V - E + F = 2
  7  * 由于V已知，E已知，F就可以求出来了。
  8  * 由于欧拉定理是对一张无向连通图成立的，如果图有多个连通块的时候需要对欧拉定理做一些
  9  * 修改。由于多个有向图的面共享最外边的面，所以设联通块的个数为n
 10  * V - E + F = 2 * n , 但是需要减去n个联通块共享的最大平面
 11  * 所以 F = n + 1 + E - V;
 12  * DATE: 2010年 07月 08日 星期四 14:49:41 CST
 13  * COMM:5
 14  * */
 15 const int N = 64;
 16 const double eps = 1e-8;
 17 int n, vis[N], g[N][N];
 18 double r[N];
 19 struct point_t {
 20     double x, y;
 21     point_t(){}
 22     point_t(double a, double b){x = a, y = b;} 
 23 }c[N];
 24 
 25 int dcmp(double x) { return (x > eps) - (x < -eps);} 
 26 bool operator < (point_t a,point_t b) 
 27 {
 28   if (dcmp(a.x - b.x)) {
 29       return a.x < b.x;
 30   }
 31   return dcmp(a.y - b.y) < 0;
 32 }
 33 
 34 point_t operator + (point_t a, point_t b) { return point_t(a.x+b.x, a.y+b.y);}
 35 point_t operator - (point_t a, point_t b) { return point_t(a.x-b.x, a.y-b.y);}
 36 double dist(point_t a, point_t b) { return hypot(a.x-b.x, a.y-b.y);}
 37 double sqr(double x) { return x * x;}
 38 point_t normal(point_t a) { return point_t(a.x / hypot(a.x, a.y), a.y / hypot(a.x, a.y));}
 39 point_t scale(point_t a, double fac) { return point_t(a.x * fac, a.y * fac);}
 40 bool intersect(point_t c1, double r1, point_t c2, double r2, point_t &a, point_t &b)
 41 {
 42   double d = dist(c1, c2);
 43   if (d < fabs(r1 - r2) - eps || d > r1 + r2 + eps) {
 44       return false;
 45   }
 46   double len = (sqr(r1) - sqr(r2) + sqr(d)) / 2.0 / d;
 47   double h = sqrt(sqr(r1) - sqr(len));
 48   point_t t = normal(c2 - c1);
 49   point_t p = c1 + scale(t, len);
 50   point_t v = scale(point_t(-t.y, t.x), h);
 51   a = p + v, b = p -v;
 52   return true;
 53 }
 54 
 55 void init()
 56 {
 57   int i;
 58   memset(g, 0, sizeof(g));
 59   memset(vis, 0, sizeof(vis));
 60   for (i = 0;i < n;i++) {
 61       g[i][i] = 1;
 62   }
 63 }
 64 
 65 int main()
 66 {
 67   int testcase, i, j, k;
 68   scanf("%d", &testcase);
 69   while (testcase--) {
 70       scanf("%d", &n);
 71       set <point_t> allpoint, p[64];
 72       for (i = 0;i < n;i++) {
 73           scanf("%lf %lf %lf", &c[i].x, &c[i].y, &r[i]);
 74       }
 75       init();
 76       for (i = 0;i < n;i++) {
 77           for (j = i + 1;j < n;j++) {
 78               point_t a, b;
 79               if (intersect(c[i], r[i], c[j], r[j], a, b)) {
 80                   allpoint.insert(a), allpoint.insert(b);
 81                   p[i].insert(a), p[i].insert(b);
 82                   p[j].insert(a), p[j].insert(b);
 83                   g[i][j] = g[j][i] = 1;
 84               }
 85           }
 86       }
 87       for (k = 0;k < n;k++) {
 88           for (i = 0;i < n;i++) {
 89               for (j = 0;j < n;j++) {
 90                   g[i][j] |= g[i][k] & g[k][j];
 91               }
 92           }
 93       }
 94       int f = 1;
 95       for (i = 0;i < n;i++) {
 96           f += p[i].size();
 97           if (!vis[i]) {
 98               f += 1;
 99               for (j = 0;j < n;j++) {
100                   vis[j] |= g[i][j];
101               }
102           }
103       }
104       f -= allpoint.size();
105       printf("%d\n", f);
106   } 
107   return 0;
108 }
109 
110 

schindlerlee 2010-07-08 22:06 发表评论

schindlerlee 2010-07-08 21:34 发表评论

schindlerlee 2010-07-07 01:48 发表评论

 1 const int N = 100010;
 2 
 3 struct point_t {
 4     double x, y;
 5 }p[N], Y[N];
 6 
 7 double sqr(double x) { return x * x;}
 8 bool cmp1(const point_t &a, const point_t &b)
 9 {
10   if (a.x != b.x) {
11       return a.x < b.x;
12   }
13   return a.y < b.y;
14 }
15 
16 bool cmp2(const point_t &a,const point_t &b)
17 {
18   if (a.y != b.y) {
19       return a.y < b.y;
20   }
21   return a.x < b.x;
22 }
23 
24 const double inf = 1e100;
25 double dist(point_t a,point_t b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}
26 int top;
27 
28 double divide(int beg, int end)
29 {
30   double ans = inf;
31   int i,j;
32   if (end < beg + 3) {
33       for (i = beg;i <= end;i++) {
34           for (j = i + 1;j <= end;j++) {
35               ckmin(ans, dist(p[i], p[j]));
36           }
37       }
38       return ans;
39   }
40   int mid = (beg + end) >> 1, cnt;
41   ckmin(ans, divide(beg, mid));
42   ckmin(ans, divide(mid + 1, end));
43   for (i = beg, top = 0;i <= end;i++) {
44       if (fabs(p[i].x - p[mid].x) < ans) {
45           Y[top++] = p[i];
46       }
47   }
48   sort(Y, Y + top, cmp2);
49   for (i = 0;i < top;i++) {
50       for (cnt = 0,j = i + 1;j < top && cnt < 7;cnt++, j++) {
51           ckmin(ans, dist(Y[i], Y[j]));
52       }
53   }
54   return ans;
55 }
56 
57 int n;
58 void proc()
59 {
60   int i,j,k;
61   sort(p, p + n, cmp1);
62   double ans = divide(0, n - 1);
63   printf("%.2f\n", ans/2.0);
64 }
65 
66 int main()
67 {
68   int i,j,k;
69   while (scanf("%d", &n) == 1 && n) {
70       for (i = 0;i < n;i++) {
71           scanf("%lf %lf", &p[i].x, &p[i].y);
72       }
73       proc();
74   }
75   return 0;
76 }
77 

schindlerlee 2010-07-07 01:44 发表评论

schindlerlee 2010-07-07 01:39 发表评论

schindlerlee 2010-07-07 01:34 发表评论

schindlerlee 2010-06-21 20:13 发表评论

 1 
 2 const int N = 1024;
 3 struct F {
 4     int v[4];
 5     F(){}
 6     F(int a,int b,int c){ v[0] = a, v[1] = b, v[2] = c, v[3] = v[0];}
 7 };
 8 
 9 struct point_t {
10     double x, y, z;
11     point_t (){}
12     point_t (double a, double b, double c){x = a, y = b, z = c;}
13 };
14 point_t operator +(point_t a, point_t b) { return point_t (a.x + b.x, a.y + b.y, a.z + b.z);}
15 point_t operator -(point_t a, point_t b) { return point_t (a.x - b.x, a.y - b.y, a.z - b.z);}
16 
17 double dot_mul(point_t a, point_t b) { return a.x * b.x + a.y * b.y + a.z * b.z;}
18 point_t cross_mul(point_t a,point_t b)
19 {
20     return point_t (a.y*b.z - b.y*a.z ,
21                     a.z*b.x - b.z*a.x ,
22                     a.x*b.y - b.x*a.y);
23 }
24 
25 double area(point_t a, point_t b)
26 {
27   point_t v = cross_mul(a, b);
28   return sqrt(0.0 + v.x * v.x + v.y * v.y + v.z * v.z) / 2;
29 }
30 
31 point_t p[N];
32 int vis[N][N], n;
33 
34 int main()
35 {
36   int i, j, k;
37   scanf("%d", &n);
38   for (i = 0;i < n;i++) {
39       scanf("%lf %lf %lf", &p[i].x, &p[i].y, &p[i].z);
40   }
41   vector<F> cur;
42   cur.pb(F(0, 1, 2)), cur.pb(F(2, 1, 0));
43   for (i = 3;i < n;i++) {
44       vector<F> next;
45       for (j = 0;j < cur.size();j++) {
46           F f = cur[j];
47           point_t v = cross_mul(p[f.v[1]] - p[f.v[0]],
48                                 p[f.v[2]] - p[f.v[1]]);
49           int val = dot_mul(v, p[i] - p[f.v[1]]) < 0 ? -1 : 1;
50           if (val < 0) {
51               next.pb(f);
52           }
53           for (k = 0;k < 3;k++) {
54               if (vis[f.v[k+1]][f.v[k]] == 0) {
55                   vis[f.v[k]][f.v[k+1]] = val;
56               }else { //http://www.cppblog.com/schindlerlee
57                   if (vis[f.v[k+1]][f.v[k]] != val) {
58                       if (val > 0) {
59                           next.pb(F(f.v[k], f.v[k+1], i));
60                       }else {
61                           next.pb(F(f.v[k+1], f.v[k], i));
62                       }
63                   }
64                   vis[f.v[k+1]][f.v[k]] = 0;
65               }
66           }
67       }
68       cur = next;
69   }
70   double ans = 0;
71   for (i = 0;i < cur.size();i++) {
72       F f = cur[i];
73       ans += area(p[f.v[0]] - p[f.v[1]], p[f.v[2]] - p[f.v[1]]);
74   }
75   printf("%.3f\n", ans);
76   return 0;
77 }

schindlerlee 2010-06-16 12:02 发表评论

  1 
  2 /*
  3  * SOUR:spoj1182
  4  * ALGO:dp, number theory, binary search
  5  * DATE: 2010年 06月 08日 星期二 19:47:51 CST
  6  * COMM:5
  7  * */
  8 #include<iostream>
  9 #include<cstdio>
 10 #include<cstdlib>
 11 #include<cstring>
 12 #include<algorithm>
 13 #include<queue>
 14 #include<vector>
 15 #include<map>
 16 using namespace std;
 17 #define pb(x) push_back(x)
 18 //#define X first
 19 //#define Y second
 20 typedef vector < int >vi;
 21 typedef pair < int, int >pii;
 22 typedef long long LL;
 23 typedef unsigned long long ULL;
 24 typedef unsigned int uint;
 25 
 26 template <class T> void ckmin(T &a,T b) { if (a > b) { a = b; } }
 27 template <class T> void ckmax(T &a,T b) { if (a < b) { a = b; } }
 28 int countbit(int n) { return n == 0 ? 0 : 1 + countbit(n & (n - 1)); }
 29 
 30 const int maxint = 0x7fffffff;
 31 const long long max64 = 0x7fffffffffffffffll;
 32 int cnt[40][40], sum[40];
 33 int X, Y, K;
 34 
 35 void pre()
 36      //算出cnt[长度][含多少个1]的方案数
 37 {
 38   int i,j;
 39   cnt[0][0] = 1;
 40   for (i = 1;i <= 32;i++) {
 41       cnt[i][0] = cnt[i-1][0];
 42       for (j = 1;j <= 32;j++) {
 43           cnt[i][j] = cnt[i-1][j] + cnt[i-1][j-1];
 44       }
 45   }
 46 }
 47 
 48 int num[40], top;
 49 int summ(uint X, int R, bool flag = false)
 50 {
 51   memset(num, 0, sizeof(num));
 52   top = 1;
 53   while (X) {
 54       num[top++] = X & 1;
 55       X >>= 1;
 56   }
 57   if (flag) {
 58       for (int i = 1;i <= top;i++) {
 59           if (num[i] == 0) {
 60               num[i] = 1;
 61               for (int j = i - 1;j >= 1;j--) {
 62                   num[j] = 0;
 63               }
 64               if (i == top) { top++; }
 65               break;
 66           }
 67       }
 68   }
 69   int ans = 0, one = 0, i;
 70   for (i = top - 1;i >= 1;i--) {
 71       if (R >= one && num[i] == 1) {
 72           ans += cnt[i - 1][R - one];
 73           one++;
 74       }
 75   }
 76   return ans;
 77 }
 78 
 79 int summarize(uint X, uint Y, int digit)
 80      //[X, Y] 中1的个数为digit的 数字个数
 81 { return summ(Y, digit, 1) - summ(X, digit, 0); }
 82 
 83 void proc()
 84 {
 85   int i, j, one = -1;
 86   memset(sum, 0, sizeof(sum));
 87   for (i = 0;i < 32;i++) {
 88       sum[i] = summarize(X, Y, i) ;
 89       if (K  > sum[i]) {
 90           K -= sum[i];
 91       }else {
 92           one = i;
 93           break;
 94       }
 95   }
 96   if (Y < X) { swap(X, Y); }
 97   int left = X, right = Y;
 98   while (left < right) { //binary search the value expected
 99       int mid = (left + right + 1) / 2;
100       if (summarize(X, mid, one) <= K) {
101           left = mid;
102       }else {
103           right = mid - 1;
104       }
105   }
106   while (countbit(left) != one) { left --; } // attention
107 
108   int ans = 0;
109   for (i = 0;i < 32;i++) {
110       if (left & (1 << i)) {
111           ans |= 1 << i;
112       }
113   }
114   printf("%d\n", ans);
115 }
116 
117 int main()
118 {
119   int i, j, testcase;
120   pre();
121   scanf("%d", &testcase);
122   while (testcase-- ) {
123       scanf("%d %d %d", &X, &Y, &K);
124       proc();
125   }
126   return 0;
127 }
128 

schindlerlee 2010-06-11 00:39 发表评论

  1 /*
  2  * SOUR:ural 1057
  3  * ALGO:number theory and binary tree, in other word enumerate the highest digit,
  4  *      and use dp to reduce calculation.
  5  * DATE: 2010年 06月 08日 星期二 16:44:45 CST
  6  * COMM:
  7  * */
  8 
  9 using namespace std;
 10 #define pb(x) push_back(x)
 11 #define X first
 12 #define Y second
 13 typedef vector < int >vi;
 14 typedef pair < int, int >pii;
 15 typedef long long LL;
 16 template <class T> void ckmin(T &a,T b) { if (a > b) { a = b; } }
 17 template <class T> void ckmax(T &a,T b) { if (a < b) { a = b; } }
 18 int countbit(int n) { return n == 0 ? 0 : 1 + countbit(n & (n - 1)); }
 19 
 20 const int maxint = 0x7fffffff;
 21 const long long max64 = 0x7fffffffffffffffll;
 22 int X, Y, K, B;
 23 int cnt[40][40];
 24 
 25 void pre ()
 26 {
 27   int i, j;
 28   cnt[0][0] = 1;
 29   for (i = 1;i <= 32;i++) {
 30       cnt[i][0] = cnt[i-1][0];
 31       for (j = 1;j <= 32;j++) {
 32           cnt[i][j] = cnt[i-1][j] + cnt[i-1][j-1];
 33       }
 34   }
 35 }
 36 
 37 void changeBase(int X, int num[], int &top)
 38 {
 39   top = 1;
 40   while (X > 0) {
 41       num[top++] = X % B;
 42       X /= B;
 43   }
 44 }
 45 
 46 void plus_one(int num[], int &top)
 47 {
 48   int i,j;
 49   for (i = 1;i <= top;i++) {
 50       if (num[i] == 0) {
 51           num[i] = 1;
 52           for (j = i - 1;j >= 1;j--) {
 53               num[j] = 0;
 54           }
 55           break;
 56       }
 57   }
 58   if (i == top) {
 59       top++;
 60   }
 61 }
 62 
 63 bool floor(int num[], int top)
 64 {
 65   int i,j;
 66   for (i = top - 1;i >= 1;i--) {
 67       if (num[i] > 1) {
 68           for (j = i;j >= 1;j--) {
 69               num[j] = 1;
 70           }
 71           break;
 72       }
 73   }
 74   if (i >= 1) {
 75       return true;
 76   }
 77   return false;
 78 }
 79 
 80 int num[40], top;
 81 int proc(int X,bool flag = false)
 82 {
 83   memset(num, 0, sizeof(num));
 84   changeBase(X, num, top);
 85   if (floor(num, top) || flag) {
 86       plus_one(num, top);
 87   }
 88 
 89   int ans = 0, sum = 0, i;
 90   for (i = top - 1;i >= 1;i--) {
 91       if (K >= sum && num[i] == 1) {
 92           ans += cnt[i-1][K - sum];
 93           sum++;
 94       }
 95   }
 96   return ans;
 97 }
 98 
 99 int main()
100 {
101   pre();
102   int num[40], top, ans;
103   cin >> X >> Y >> K >> B;
104   ans = proc(Y, 1) - proc(X);
105   cout << ans << endl;
106   return 0;
107 }

schindlerlee 2010-06-08 23:31 发表评论

 1 
 2 const int N = 50100;
 3 int a[N],n,len;
 4 int main()
 5 {
 6   int i,j,k;
 7   scanf("%d",&n);
 8   a[1] = 1,len = 1;
 9   for (k = 2;k <= n;k++) {
10       i = len;
11       while (i > 1) {
12           a[i] = a[i/2];
13           i /= 2;
14       }
15       a[1] = k;
16       a[++len] = 1;
17   }
18   for (i = 1;i <= len;i++) {
19       printf("%d ",a[i]);
20   }
21   putchar(10);
22   return 0;
23 }
24 

schindlerlee 2010-03-29 00:51 发表评论

 1 
 2 scanf("%d\n",&n);
 3 for (i = 0;i < n;i++) {
 4   scanf("%d",a + i);
 5 }
 6 int L = 0,R = n - 1,time1 = 0,time2 = 0,ans1 = 0,ans2 = 0;
 7 while (L <= R) {
 8   if (time1 < time2) {
 9       time1 += a[L++] ,ans1 ++;
10   }else if (time1 > time2) {
11       time2 += a[R--] ,ans2 ++;
12   }else {
13       time1 += a[L++] ,ans1 ++;
14   }
15 }
16 printf("%d %d\n",ans1,ans2);

schindlerlee 2010-03-28 01:17 发表评论

 1 
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 using namespace std;
 8 typedef long long LL;
 9 const int maxint = 0x7fffffff;
10 const long long max64 = 0x7fffffffffffffffll;
11 const int Debug = 1;
12 const int M = 228;
13 const int N = 13;
14 const int inf = 1000000;
15 
16 int dp[M][N][N][N][N], m, n, a[N], b[N];
17 void ckmin(int &a, int b) { if (a > b) { a = b; } }
18 int dfs(int balloon,int p0,int p1,int p2,int p3)
19 {
20   if (dp[balloon][p0][p1][p2][p3] < inf) {
21       return dp[balloon][p0][p1][p2][p3];
22   }
23   if (balloon >= m) {
24       return 0;
25   }
26   for (int i = 1;i <= n;i++) {
27       if (b[i] == 1 && (p0 == i)) { continue; }
28       if (b[i] == 2 && (p0 == i || p1 == i)) { continue; }
29       if (b[i] == 3 && (p0 == i || p1 == i || p2 == i)) { continue; }
30       if (b[i] == 4 && (p0 == i || p1 == i || p2 == i || p3 == i)) { continue; }
31       ckmin(dp [balloon][p0][p1][p2][p3] , dfs(balloon + a[i],i,p0,p1,p2) + 1);
32   }
33   if (dp [balloon][p0][p1][p2][p3] >= inf) {
34       dp [balloon][p0][p1][p2][p3] = dfs(balloon,0,p0,p1,p2) + 1;
35   }
36   return dp [balloon][p0][p1][p2][p3];
37 }
38//http://www.cppblog.com/schindlerlee
39 int main()
40 {
41     int i, j, k, p[4], tmp;
42     memset(dp,127,sizeof(dp));
43     //printf("%d\n",dp[0][0][0][0][0]);
44     scanf("%d %d", &m, &n);
45     for (i = 1; i <= n; i++) {
46         scanf("%d %d", a + i, b + i);
47     }
48 
49     printf("%d\n",    dfs(0,0,0,0,0));
50     return 0;
51 }
52 

schindlerlee 2010-03-20 13:54 发表评论