A http://hihocoder.com/problemset/problem/1227
题意：给出平面上m个点，任选一个点为圆心，选最小的半径使得恰好n个点在圆内。
解法：枚举圆心，然后对所有点到该圆心距离排序，取第n大的距离作为半径，若第n+1大的在圆内或圆上不合法。
1 //#define debug 2 //#define txtout 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cstring> 6 #include<cmath> 7 #include<cctype> 8 #include<ctime> 9 #include<iostream> 10 #include<algorithm> 11 #include<vector> 12 #include<queue> 13 #include<stack> 14 #include<map> 15 #include<set> 16 #define mt(a,b) memset(a,b,sizeof(a)) 17 using namespace std; 18 typedef long long LL; 19 const double eps=1e-8; 20 const double pi=acos(-1.0); 21 const int inf=0x3f3f3f3f; 22 const int M=1e2+10; 23 struct point { 24 double x,y; 25 } p[M]; 26 double dist[M]; 27 int n,m; 28 29 double Square(double x) { ///平方 30 return x*x; 31 } 32 double Distance(point a,point b) { ///平面两点距离 33 return sqrt(Square(a.x-b.x)+Square(a.y-b.y)); 34 } 35 36 int choose(point c) { 37 for(int i=0; i<m; i++) { 38 dist[i]=Distance(c,p[i]); 39 } 40 sort(dist,dist+m); 41 double r=dist[n-1]; 42 int int_r=(int)(r+1); 43 if(n<m&&dist[n]<int_r+eps) 44 return inf; 45 return int_r; 46 } 47 int solve() { 48 if(n>m) return -1; 49 int res=inf; 50 for(int i=0; i<m; i++) { 51 res=min(res,choose(p[i])); 52 } 53 if(res==inf) res=-1; 54 return res; 55 } 56 int main() { 57 #ifdef txtout 58 freopen("in.txt","r",stdin); 59 freopen("out.txt","w",stdout); 60 #endif 61 int t; 62 while(~scanf("%d",&t)) { 63 while(t--) { 64 scanf("%d%d",&m,&n); 65 for(int i=0; i<m; i++) { 66 scanf("%lf%lf",&p[i].x,&p[i].y); 67 } 68 printf("%d ",solve()); 69 } 70 } 71 return 0; 72 }
B http://hihocoder.com/problemset/problem/1228
题意：模拟一行文本的输入操作。输入文本长度限制m，操作序列string，输出最后的文本。
操作L将光标左移，R光标右移，S切换插入和复写的输入模式，D删右边一个或选中区间，B删左边一个，C选区间，V将缓冲区复制一份。完全符合计算机复制粘贴等，细心模拟题。
解法：读题，模拟。
1 //#define debug 2 //#define txtout 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cstring> 6 #include<cmath> 7 #include<cctype> 8 #include<ctime> 9 #include<iostream> 10 #include<algorithm> 11 #include<vector> 12 #include<queue> 13 #include<stack> 14 #include<map> 15 #include<set> 16 #define mt(a,b) memset(a,b,sizeof(a)) 17 using namespace std; 18 typedef long long LL; 19 const double eps=1e-8; 20 const double pi=acos(-1.0); 21 const int inf=0x3f3f3f3f; 22 const int M=1e4+10; 23 char input[M]; 24 char output[M]; 25 char buffer[M]; 26 char save[M]; 27 int limit; 28 int length_of_output; 29 int length_of_buffer; 30 int index_of_caret; 31 int index_of_copy; 32 bool overwrite_mode; 33 bool start; 34 void init(){ 35 index_of_caret=0; 36 length_of_output=0; 37 overwrite_mode=false; 38 start=false; 39 } 40 void Insert(int id,char c){ 41 length_of_output++; 42 for(int i=length_of_output-1;i>=id;i--){ 43 output[i]=output[i-1]; 44 } 45 output[id]=c; 46 } 47 void Delete(int x,int y){ 48 for(int i=y+1;i<length_of_output;i++){ 49 output[x+i-y-1]=output[i]; 50 } 51 length_of_output-=(y-x+1); 52 } 53 void Copy(int x,int y){ 54 length_of_buffer=0; 55 for(int i=x;i<=y;i++){ 56 buffer[length_of_buffer++]=output[i]; 57 } 58 } 59 void Flip(bool &a){ 60 a=!a; 61 } 62 void solve_L(){ 63 if(index_of_caret) index_of_caret--; 64 } 65 void solve_R(){ 66 if(index_of_caret<length_of_output) index_of_caret++; 67 } 68 void solve_S(){ 69 Flip(overwrite_mode); 70 } 71 void solve_D(){ 72 if(start){ 73 if(index_of_caret<index_of_copy){ 74 Delete(index_of_caret,index_of_copy-1); 75 } 76 else{ 77 Delete(index_of_copy,index_of_caret-1); 78 index_of_caret=index_of_copy; 79 } 80 Flip(start); 81 return ; 82 } 83 if(index_of_caret<length_of_output){ 84 Delete(index_of_caret,index_of_caret); 85 } 86 } 87 void solve_B(){ 88 if(index_of_caret){ 89 Delete(index_of_caret-1,index_of_caret-1); 90 index_of_caret--; 91 } 92 } 93 void solve_C(){ 94 if(start){ 95 if(index_of_caret<index_of_copy){ 96 Copy(index_of_caret,index_of_copy-1); 97 } 98 else{ 99 Copy(index_of_copy,index_of_caret-1); 100 } 101 } 102 else{ 103 index_of_copy=index_of_caret; 104 length_of_buffer=0; 105 } 106 Flip(start); 107 } 108 void solve_V(){ 109 if(overwrite_mode){ 110 if(index_of_caret+length_of_buffer>limit) return ; 111 for(int i=0;i<length_of_buffer;i++){ 112 output[index_of_caret+i]=buffer[i]; 113 } 114 index_of_caret+=length_of_buffer; 115 length_of_output=max(length_of_output,index_of_caret); 116 } 117 else{ 118 if(length_of_output+length_of_buffer>limit) return ; 119 int length_of_save=0; 120 for(int i=index_of_caret;i<length_of_output;i++){ 121 save[length_of_save++]=output[i]; 122 } 123 for(int i=0;i<length_of_buffer;i++){ 124 output[index_of_caret+i]=buffer[i]; 125 } 126 index_of_caret+=length_of_buffer; 127 for(int i=0;i<length_of_save;i++){ 128 output[index_of_caret+i]=save[i]; 129 } 130 length_of_output+=length_of_buffer; 131 } 132 } 133 void add(char c){ 134 if(overwrite_mode){ 135 if(index_of_caret==length_of_output&&length_of_output==limit) return ; 136 output[index_of_caret]=c; 137 if(index_of_caret==length_of_output) length_of_output++; 138 } 139 else{ 140 if(length_of_output==limit) return ; 141 Insert(index_of_caret,c); 142 } 143 index_of_caret++; 144 } 145 void solve_by_type(char c){ 146 if(c=='L') return solve_L(); 147 if(c=='R') return solve_R(); 148 if(c=='D') return solve_D(); 149 if(c=='C') return solve_C(); 150 start=false; 151 if(c=='B') return solve_B(); 152 if(c=='S') return solve_S(); 153 if(c=='V') return solve_V(); 154 return add(c); 155 } 156 void solve(){ 157 init(); 158 for(int i=0;input[i];i++){ 159 solve_by_type(input[i]); 160 } 161 output[length_of_output]=0; 162 if(length_of_output==0) strcpy(output,"NOTHING"); 163 } 164 int main(){ 165 #ifdef txtout 166 freopen("in.txt","r",stdin); 167 freopen("out.txt","w",stdout); 168 #endif 169 int t; 170 while(~scanf("%d",&t)){ 171 while(t--){ 172 scanf("%d%s",&limit,input); 173 solve(); 174 puts(output); 175 } 176 } 177 return 0; 178 }
H http://hihocoder.com/problemset/problem/1234
题意：给一个边长1的正方形，每次选每条边中点构成新的正方形，重复1000次，输入一个坐标k，求x=k这条直线与该图形交点个数。
解法：精度至少1e-10，枚举前30个竖线的x坐标存数组，然后测输入的坐标在哪个范围，每往前走一个范围答案+4，如果离0.5非常近，就是2000.
1 //#define debug 2 //#define txtout 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cstring> 6 #include<cmath> 7 #include<cctype> 8 #include<ctime> 9 #include<iostream> 10 #include<algorithm> 11 #include<vector> 12 #include<queue> 13 #include<stack> 14 #include<map> 15 #include<set> 16 #define mt(a,b) memset(a,b,sizeof(a)) 17 using namespace std; 18 typedef long long LL; 19 const double eps=1e-10; 20 const double pi=acos(-1.0); 21 const int inf=0x3f3f3f3f; 22 const int M=1e2+10; 23 double x; 24 double y[M]; 25 bool zero(double x){ 26 return (x>0?x:-x)<eps; 27 } 28 void init(){ 29 double add=0.25; 30 y[0]=0; 31 for(int i=1;i<30;i++){ 32 y[i]=y[i-1]+add; 33 add*=0.5; 34 } 35 } 36 int solve(){ 37 int res=0; 38 for(int i=0;i<30;i++){ 39 if(zero(x-y[i])) return -1; 40 if(x<y[i]) return res; 41 res+=4; 42 } 43 return 2000; 44 } 45 int main(){ 46 #ifdef txtout 47 freopen("in.txt","r",stdin); 48 freopen("out.txt","w",stdout); 49 #endif 50 init(); 51 int t; 52 while(~scanf("%d",&t)){ 53 while(t--){ 54 scanf("%lf",&x); 55 printf("%d ",solve()); 56 } 57 } 58 return 0; 59 }
end