1001Apple
Problem Description Apple is Taotao's favourite fruit. In his backyard, there are three apple trees with coordinates (x1,y1), (x2,y2), and (x3,y3). Now Taotao is planning to plant a new one, but he is not willing to take these trees too close. He believes that the new apple tree should be outside the circle which the three apple trees that already exist is on. Taotao picked a potential position (x,y) of the new tree. Could you tell him if it is outside the circle or not? Input The first line contains an integer T, indicating that there are T(T≤30) cases. In the first line of each case, there are eight integers x1,y1,x2,y2,x3,y3,x,y, as described above. The absolute values of integers in input are less than or equal to 1,000,000,000,000. It is guaranteed that, any three of the four positions do not lie on a straight line. Output For each case, output "Accepted" if the position is outside the circle, or "Rejected" if the position is on or inside the circle. Sample Input 3 -2 0 0 -2 2 0 2 -2 -2 0 0 -2 2 0 0 2 -2 0 0 -2 2 0 1 1 Sample Output Accepted Rejected Rejected
大意是给你三个点，绘制一个圆形区域，再输入一个点，问在不在圆内
难点：高精度
1 #include <cmath> 2 #include <map> 3 #include <vector> 4 #include <cstdio> 5 #include <cstdlib> 6 #include <iostream> 7 #include <algorithm> 8 #include <cstring> 9 #include <set> 10 #include <bitset> 11 #include <memory.h> 12 #include <functional> 13 #include <queue> 14 #include <fstream> 15 #include <ctime> 16 #include <deque> 17 #include <utility> 18 #include <stack> 19 #include <sstream> 20 #include <list> 21 #include <cctype> 22 #include <numeric> 23 #include <iomanip> 24 #include <assert.h> 25 #define EPS 1e-8 26 using namespace std; 27 const int maxn = 550; 28 typedef long long LL; 29 30 #define MAX_L 2005 31 32 class bign 33 { 34 public: 35 int len, s[MAX_L]; 36 bign(); 37 bign(const char*); 38 bign(int); 39 bool sign; 40 string toStr() const; 41 friend istream& operator>>(istream &,bign &); 42 friend ostream& operator<<(ostream &,bign &); 43 bign operator=(const char*); 44 bign operator=(int); 45 bign operator=(const string); 46 bool operator>(const bign &) const; 47 bool operator>=(const bign &) const; 48 bool operator<(const bign &) const; 49 bool operator<=(const bign &) const; 50 bool operator==(const bign &) const; 51 bool operator!=(const bign &) const; 52 bign operator+(const bign &) const; 53 bign operator++(); 54 bign operator++(int); 55 bign operator+=(const bign&); 56 bign operator-(const bign &) const; 57 bign operator--(); 58 bign operator--(int); 59 bign operator-=(const bign&); 60 bign operator*(const bign &)const; 61 bign operator*(const int num)const; 62 bign operator*=(const bign&); 63 bign operator/(const bign&)const; 64 bign operator/=(const bign&); 65 bign operator%(const bign&)const; 66 bign factorial()const; 67 bign Sqrt()const; 68 bign pow(const bign&)const; 69 void clean(); 70 ~bign(); 71 }; 72 #define max(a,b) a>b ? a : b 73 #define min(a,b) a<b ? a : b 74 75 bign::bign() 76 { 77 memset(s, 0, sizeof(s)); 78 len = 1; 79 sign = 1; 80 } 81 82 bign::bign(const char *num) 83 { 84 *this = num; 85 } 86 87 bign::bign(int num) 88 { 89 *this = num; 90 } 91 92 string bign::toStr() const 93 { 94 string res; 95 res = ""; 96 for (int i = 0; i < len; i++) 97 res = (char)(s[i] + '0') + res; 98 if (res == "") 99 res = "0"; 100 if (!sign&&res != "0") 101 res = "-" + res; 102 return res; 103 } 104 105 istream &operator>>(istream &in, bign &num) 106 { 107 string str; 108 in>>str; 109 num=str; 110 return in; 111 } 112 113 ostream &operator<<(ostream &out, bign &num) 114 { 115 out<<num.toStr(); 116 return out; 117 } 118 119 bign bign::operator=(const char *num) 120 { 121 memset(s, 0, sizeof(s)); 122 char a[MAX_L] = ""; 123 if (num[0] != '-') 124 strcpy(a, num); 125 else 126 for (int i = 1; i < strlen(num); i++) 127 a[i - 1] = num[i]; 128 sign = !(num[0] == '-'); 129 len = strlen(a); 130 for (int i = 0; i < strlen(a); i++) 131 s[i] = a[len - i - 1] - 48; 132 return *this; 133 } 134 135 bign bign::operator=(int num) 136 { 137 char temp[MAX_L]; 138 sprintf(temp, "%d", num); 139 *this = temp; 140 return *this; 141 } 142 143 bign bign::operator=(const string num) 144 { 145 const char *tmp; 146 tmp = num.c_str(); 147 *this = tmp; 148 return *this; 149 } 150 151 bool bign::operator<(const bign &num) const 152 { 153 if (sign^num.sign) 154 return num.sign; 155 if (len != num.len) 156 return len < num.len; 157 for (int i = len - 1; i >= 0; i--) 158 if (s[i] != num.s[i]) 159 return sign ? (s[i] < num.s[i]) : (!(s[i] < num.s[i])); 160 return !sign; 161 } 162 163 bool bign::operator>(const bign&num)const 164 { 165 return num < *this; 166 } 167 168 bool bign::operator<=(const bign&num)const 169 { 170 return !(*this>num); 171 } 172 173 bool bign::operator>=(const bign&num)const 174 { 175 return !(*this<num); 176 } 177 178 bool bign::operator!=(const bign&num)const 179 { 180 return *this > num || *this < num; 181 } 182 183 bool bign::operator==(const bign&num)const 184 { 185 return !(num != *this); 186 } 187 188 bign bign::operator+(const bign &num) const 189 { 190 if (sign^num.sign) 191 { 192 bign tmp = sign ? num : *this; 193 tmp.sign = 1; 194 return sign ? *this - tmp : num - tmp; 195 } 196 bign result; 197 result.len = 0; 198 int temp = 0; 199 for (int i = 0; temp || i < (max(len, num.len)); i++) 200 { 201 int t = s[i] + num.s[i] + temp; 202 result.s[result.len++] = t % 10; 203 temp = t / 10; 204 } 205 result.sign = sign; 206 return result; 207 } 208 209 bign bign::operator++() 210 { 211 *this = *this + 1; 212 return *this; 213 } 214 215 bign bign::operator++(int) 216 { 217 bign old = *this; 218 ++(*this); 219 return old; 220 } 221 222 bign bign::operator+=(const bign &num) 223 { 224 *this = *this + num; 225 return *this; 226 } 227 228 bign bign::operator-(const bign &num) const 229 { 230 bign b=num,a=*this; 231 if (!num.sign && !sign) 232 { 233 b.sign=1; 234 a.sign=1; 235 return b-a; 236 } 237 if (!b.sign) 238 { 239 b.sign=1; 240 return a+b; 241 } 242 if (!a.sign) 243 { 244 a.sign=1; 245 b=bign(0)-(a+b); 246 return b; 247 } 248 if (a<b) 249 { 250 bign c=(b-a); 251 c.sign=false; 252 return c; 253 } 254 bign result; 255 result.len = 0; 256 for (int i = 0, g = 0; i < a.len; i++) 257 { 258 int x = a.s[i] - g; 259 if (i < b.len) x -= b.s[i]; 260 if (x >= 0) g = 0; 261 else 262 { 263 g = 1; 264 x += 10; 265 } 266 result.s[result.len++] = x; 267 } 268 result.clean(); 269 return result; 270 } 271 272 bign bign::operator * (const bign &num)const 273 { 274 bign result; 275 result.len = len + num.len; 276 277 for (int i = 0; i < len; i++) 278 for (int j = 0; j < num.len; j++) 279 result.s[i + j] += s[i] * num.s[j]; 280 281 for (int i = 0; i < result.len; i++) 282 { 283 result.s[i + 1] += result.s[i] / 10; 284 result.s[i] %= 10; 285 } 286 result.clean(); 287 result.sign = !(sign^num.sign); 288 return result; 289 } 290 291 bign bign::operator*(const int num)const 292 { 293 bign x = num; 294 bign z = *this; 295 return x*z; 296 } 297 bign bign::operator*=(const bign&num) 298 { 299 *this = *this * num; 300 return *this; 301 } 302 303 bign bign::operator /(const bign&num)const 304 { 305 bign ans; 306 ans.len = len - num.len + 1; 307 if (ans.len < 0) 308 { 309 ans.len = 1; 310 return ans; 311 } 312 313 bign divisor = *this, divid = num; 314 divisor.sign = divid.sign = 1; 315 int k = ans.len - 1; 316 int j = len - 1; 317 while (k >= 0) 318 { 319 while (divisor.s[j] == 0) j--; 320 if (k > j) k = j; 321 char z[MAX_L]; 322 memset(z, 0, sizeof(z)); 323 for (int i = j; i >= k; i--) 324 z[j - i] = divisor.s[i] + '0'; 325 bign dividend = z; 326 if (dividend < divid) { k--; continue; } 327 int key = 0; 328 while (divid*key <= dividend) key++; 329 key--; 330 ans.s[k] = key; 331 bign temp = divid*key; 332 for (int i = 0; i < k; i++) 333 temp = temp * 10; 334 divisor = divisor - temp; 335 k--; 336 } 337 ans.clean(); 338 ans.sign = !(sign^num.sign); 339 return ans; 340 } 341 342 bign bign::operator/=(const bign&num) 343 { 344 *this = *this / num; 345 return *this; 346 } 347 348 bign bign::operator%(const bign& num)const 349 { 350 bign a = *this, b = num; 351 a.sign = b.sign = 1; 352 bign result, temp = a / b*b; 353 result = a - temp; 354 result.sign = sign; 355 return result; 356 } 357 358 bign bign::pow(const bign& num)const 359 { 360 bign result = 1; 361 for (bign i = 0; i < num; i++) 362 result = result*(*this); 363 return result; 364 } 365 366 bign bign::factorial()const 367 { 368 bign result = 1; 369 for (bign i = 1; i <= *this; i++) 370 result *= i; 371 return result; 372 } 373 374 void bign::clean() 375 { 376 if (len == 0) len++; 377 while (len > 1 && s[len - 1] == ' ') 378 len--; 379 } 380 381 bign bign::Sqrt()const 382 { 383 if(*this<0)return -1; 384 if(*this<=1)return *this; 385 bign l=0,r=*this,mid; 386 while(r-l>1) 387 { 388 mid=(l+r)/2; 389 if(mid*mid>*this) 390 r=mid; 391 else 392 l=mid; 393 } 394 return l; 395 } 396 bign::~bign() 397 { 398 } 399 struct point{ 400 bign x, y; 401 }; 402 bign get_distance( point &a, point &b) 403 { 404 return ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); 405 } 406 /* 407 point get_circle_center(const point a, const point b, const point c) 408 { 409 point center; 410 bign a1 = b.x - a.x; 411 bign b1 = b.y - a.y; 412 bign c1 = (a1 * a1 + b1 * b1) / 2.0; 413 bign a2 = c.x - a.x; 414 bign b2 = c.y - a.y; 415 bign c2 = (a2 * a2 + b2 * b2) / 2.0; 416 bign d = a1 * b2 - a2 * b1; 417 center.x = a.x + (c1 * b2 - c2 * b1) / d; 418 center.y = a.y + (a1 * c2 - a2 * c1) / d; 419 return center; 420 } 421 */ 422 bign D; 423 point get_circle_center( point a, point b, point c) 424 { 425 point center; 426 bign a1 = b.x - a.x; 427 bign b1 = b.y - a.y; 428 bign c1 = (a1 * a1 + b1 * b1); 429 bign a2 = c.x - a.x; 430 bign b2 = c.y - a.y; 431 bign c2 = (a2 * a2 + b2 * b2); 432 bign d = a1 * b2 - a2 * b1; 433 D = d * 2; 434 center.x = a.x * 2 * d + (c1 * b2 - c2 * b1); 435 center.y = a.y * 2 * d + (a1 * c2 - a2 * c1); 436 return center; 437 } 438 void solve() 439 { 440 point a, b, c, d; 441 //scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y, &c.x, &c.y, &d.x, &d.y); 442 cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y; 443 /* 444 int ax, ay, bx, by, cx, cy, dx, dy; 445 cin >> ax >> ay >> bx >> by >> cx >> cy >> dx >> dy; 446 a.x = ax + 1000000000; 447 a.y = ay + 1000000000; 448 b.x = bx + 1000000000; 449 b.y = by + 1000000000; 450 c.x = cx + 1000000000; 451 c.y = cy + 1000000000; 452 d.x = dx + 1000000000; 453 d.y = dy + 1000000000; 454 */ 455 point o = get_circle_center(a, b, c); 456 a.x = a.x * D, a.y = a.y * D, d.x = d.x * D, d.y = d.y * D; 457 //cout << get_distance(o, a).toStr() << " " << get_distance(o, d).toStr() << endl; 458 if (get_distance(o, a) < get_distance(o, d)) 459 puts("Accepted"); 460 else 461 puts("Rejected"); 462 } 463 int main() 464 { 465 int test; 466 scanf("%d", &test); 467 for (int i = 0; i < test; ++i) 468 solve(); 469 return 0; 470 }