This is the logo of PKUACM 2016. More specifically, the logo is generated as follows:
1. Put four points A0(0,0), B0(0,1), C0(1,1), D0(1,0) on a cartesian coordinate system.
2. Link A0B0, B0C0, C0D0, D0A0 separately, forming square A0B0C0D0.
3. Assume we have already generated square AiBiCiDi, then square Ai+1Bi+1Ci+1Di+1 is generated by linking the midpoints of AiBi, BiCi, CiDi and DiAi successively.
4. Repeat step three 1000 times.
Now the designer decides to add a vertical line x=k to this logo( 0<= k < 0.5, and for k, there will be at most 8 digits after the decimal point). He wants to know the number of common points between the new line and the original logo.
In the first line there’s an integer T( T < 10,000), indicating the number of test cases.
Then T lines follow, each describing a test case. Each line contains an float number k, meaning that you should calculate the number of common points between line x = k and the logo.
For each test case, print a line containing one integer indicating the answer. If there are infinity common points, print -1.
3 0.375 0.001 0.478
-1 4 20
找出计算的规律即可
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 #include<math.h> 7 #include<algorithm> 8 #include<queue> 9 #include<set> 10 #include<bitset> 11 #include<map> 12 #include<vector> 13 #include<stdlib.h> 14 #include <stack> 15 using namespace std; 16 int dirx[]={0,0,-1,1}; 17 int diry[]={-1,1,0,0}; 18 #define PI acos(-1.0) 19 #define max(a,b) (a) > (b) ? (a) : (b) 20 #define min(a,b) (a) < (b) ? (a) : (b) 21 #define ll long long 22 #define eps 1e-10 23 #define MOD 1000000007 24 #define N 1000000 25 #define inf 1e12 26 double n; 27 int num[100000]; 28 29 int main() 30 { 31 int t; 32 scanf("%d",&t); 33 while(t--){ 34 scanf("%lf",&n); 35 int i; 36 double x=0; 37 double y=0.5; 38 for(i=0;;i++){ 39 if(x>=n){ 40 break; 41 } 42 x=x+y/2.0; 43 y/=2.0; 44 } 45 int w=i; 46 if(x==n){ 47 printf("-1\n"); 48 } 49 else{ 50 int ans=0; 51 for(int i=0;i<w;i++){ 52 ans+=4; 53 } 54 printf("%d\n",ans); 55 } 56 } 57 return 0; 58 }
hihoCoder #1234 : Fractal（数学简单题）
原文：http://www.cnblogs.com/UniqueColor/p/4834752.html
