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
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long LL;
const LL INF = 0xfffffff;
const int maxn = 105;
const LL MOD = 1e9+7;
double as[2000];
int main()
{
int T, ok, ans, i;
double a=0, b=0.5;
for(i = 1; i <= 1000; i++)
{
as[i] = (a+b)/2;
a = (a+b)/2;
}
double x;
scanf("%d", &T);
while(T--)
{
scanf("%lf", &x); ok = 0;
for(i = 0; i <= 1000; i++)
{
if(fabs(as[i] - x) < 1e-10)
{
ok = 1;
break;
}
if(x > as[i-1] && x < as[i])
{
ans = i;
break;
}
}
if(ok == 1) printf("-1\n");
else printf("%d\n", ans*4);
}
return 0;
}
原文：http://www.cnblogs.com/PersistFaith/p/4828696.html