zju2009.dpr 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530
  1. program zju2009;
  2. const
  3. maxn=1004;
  4. zero=1e-7;
  5. type
  6. point=record
  7. x,y:double;
  8. k:longint;
  9. end;
  10. edge=^Tedge;
  11. Tedge=record
  12. x:longint;
  13. next:edge;
  14. end;
  15. var
  16. tri:array[1..maxn*3]of record
  17. a,b,c:point;
  18. end;
  19. way:array[1..maxn,1..maxn]of boolean;
  20. used,a:array[1..maxn]of longint;
  21. check:array[1..maxn]of boolean;
  22. e_free:array[1..maxn*maxn]of edge;
  23. p:array[1..maxn]of point;
  24. v:array[1..maxn]of edge;
  25. tot,m,n,tasks:longint;
  26. x,y:double;
  27. procedure fill;
  28. var
  29. i:longint;
  30. begin
  31. for i:=1 to maxn do v[i]:=nil;
  32. // for i:=1 to maxn*maxn do dispose(e_free[i]);
  33. fillchar(tri,sizeof(tri),0);
  34. fillchar(way,sizeof(way),false);
  35. fillchar(check,sizeof(check),false);
  36. fillchar(used,sizeof(used),0);
  37. fillchar(a,sizeof(a),0);
  38. fillchar(p,sizeof(p),0);
  39. n:=0;m:=0;tot:=0;
  40. end;
  41. procedure sort(l,r:longint);
  42. var
  43. t:point;
  44. x,y:double;
  45. i,j:longint;
  46. begin
  47. x:=p[(l+r) div 2].x;
  48. y:=p[(l+r) div 2].y;
  49. i:=l;j:=r;
  50. while true do begin
  51. while (p[i].x<x)or((p[i].x=x)and(p[i].y<y)) do inc(i);
  52. while (p[j].x>x)or((p[j].x=x)and(p[j].y>y)) do dec(j);
  53. if j>i then begin
  54. t:=p[i];
  55. p[i]:=p[j];
  56. p[j]:=t;
  57. inc(i);dec(j);
  58. end
  59. else break;
  60. end;
  61. if j>l then sort(l,j);
  62. if j<r then sort(j+1,r);
  63. end;
  64. procedure init;
  65. var
  66. x,y:double;
  67. i:longint;
  68. begin
  69. readln(x,y,n);
  70. for i:=1 to n do begin
  71. readln(p[i].x,p[i].y);
  72. p[i].k:=i;
  73. v[i]:=nil;
  74. end;
  75. p[n+1].x:=0;p[n+1].y:=0;
  76. p[n+2].x:=0;p[n+2].y:=y;
  77. p[n+3].x:=x;p[n+3].y:=0;
  78. p[n+4].x:=x;p[n+4].y:=y;
  79. sort(1,n);
  80. end;
  81. procedure get_bis(x,y:point;var p1,p2:point);
  82. begin
  83. p1.x:=(x.x+y.x)/2;
  84. p1.y:=(x.y+y.y)/2;
  85. if abs(x.y-y.y)<zero then begin
  86. p2.x:=p1.x;
  87. p2.y:=1+p1.y;
  88. end
  89. else begin
  90. p2.x:=1+p1.x;
  91. p2.y:=-(p2.x-p1.x)*(y.x-x.x)/(y.y-x.y)+p1.y;
  92. end;
  93. end;
  94. procedure get_line(p1,p2:point;var a,b,c:double);
  95. begin
  96. if p1.y=p2.y then begin
  97. a:=0;c:=-p1.y;b:=1;
  98. end
  99. else if p1.x=p2.x then begin
  100. b:=0;c:=-p1.x;a:=1;
  101. end
  102. else if abs(p2.x*p1.y-p2.y*p1.x)<=zero then begin
  103. c:=0;
  104. b:=1;
  105. if p1.x=0 then a:=-p2.y/p2.x
  106. else a:=-p1.y/p1.x;
  107. end
  108. else begin
  109. c:=1;
  110. b:=-(p2.x-p1.x)/(p2.x*p1.y-p2.y*p1.x);
  111. a:=-(p2.y-p1.y)/(p1.x*p2.y-p2.x*p1.y);
  112. end;
  113. end;
  114. function oneline(p1,p2,p3,p4:point):boolean;
  115. begin
  116. oneline:=false;
  117. if abs((p2.x-p1.x)*(p4.y-p3.y)-(p2.y-p1.y)*(p4.x-p3.x))<=zero then oneline:=true;
  118. if abs((p1.x-p2.x)*(p4.y-p3.y)-(p1.y-p2.y)*(p4.x-p3.x))<=zero then oneline:=true;
  119. if abs((p2.x-p1.x)*(p3.y-p4.y)-(p2.y-p1.y)*(p3.x-p4.x))<=zero then oneline:=true;
  120. if abs((p1.x-p2.x)*(p3.y-p4.y)-(p1.y-p2.y)*(p3.x-p4.x))<=zero then oneline:=true;
  121. end;
  122. function get_inter(p1,p2,p3,p4:point;var p:point):boolean;
  123. var
  124. a1,b1,c1,a2,b2,c2:double;
  125. begin
  126. get_line(p1,p2,a1,b1,c1);
  127. get_line(p3,p4,a2,b2,c2);
  128. if oneline(p1,p2,p3,p4) then begin
  129. get_inter:=false;
  130. exit;
  131. end
  132. else get_inter:=true;
  133. if (a1=0)or(a2=0) then begin
  134. if a1=0 then begin
  135. p.y:=-c1/b1;
  136. if a2<>0 then p.x:=(-c2-b2*p.y)/a2;
  137. end;
  138. if a2=0 then begin
  139. p.y:=-c2/b2;
  140. if a1<>0 then p.x:=(-c1-b1*p.y)/a1;
  141. end;
  142. end
  143. else if (b1=0)or(b2=0) then begin
  144. if b1=0 then begin
  145. p.x:=-c1/a1;
  146. if b2<>0 then p.y:=(-c2-a2*p.x)/b2;
  147. end;
  148. if b2=0 then begin
  149. p.x:=-c2/a2;
  150. if b1<>0 then p.y:=(-c1-a1*p.x)/b1;
  151. end;
  152. end
  153. else begin
  154. p.x:=(-b2*c1+b1*c2)/(b2*a1-b1*a2);
  155. p.y:=(-a2*c1+a1*c2)/(a2*b1-a1*b2);
  156. end;
  157. end;
  158. function get_sit(p1,p2,p3:point):double;
  159. begin
  160. get_sit:=(p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
  161. end;
  162. procedure get_tang(l,k,r:longint;var p1,p2,p3,p4:longint);
  163. var
  164. xx,i:longint;
  165. begin
  166. tot:=2;
  167. fillchar(a,sizeof(a),0);
  168. fillchar(check,sizeof(check),false);
  169. a[1]:=l;a[2]:=l+1;i:=l+2;
  170. check[l]:=true;check[l+1]:=true;
  171. while i<=r do begin
  172. if not check[i] then begin
  173. while (tot>1)and(get_sit(p[a[tot-1]],p[a[tot]],p[i])<0) do begin
  174. check[a[tot]]:=false;
  175. a[tot]:=0;
  176. dec(tot);
  177. end;
  178. inc(tot);
  179. check[i]:=true;
  180. a[tot]:=i;
  181. end;
  182. inc(i);
  183. end;
  184. for i:=1 to tot do if a[i]>k then break;
  185. p1:=a[i-1];p2:=a[i];
  186. xx:=tot;
  187. for i:=a[tot] downto l do
  188. if not check[i] then begin
  189. check[i]:=true;
  190. inc(tot);
  191. a[tot]:=i;
  192. break;
  193. end;
  194. while i>=a[1] do begin
  195. if (not check[i])or(i=a[1]) then begin
  196. while (tot>xx)and(get_sit(p[a[tot-1]],p[a[tot]],p[i])<0) do begin
  197. check[a[tot]]:=false;
  198. a[tot]:=0;
  199. dec(tot);
  200. end;
  201. inc(tot);
  202. check[i]:=true;
  203. a[tot]:=i;
  204. end;
  205. dec(i);
  206. end;
  207. if a[tot]<>l then begin
  208. inc(tot);
  209. a[tot]:=l;
  210. end;
  211. for i:=tot downto 1 do
  212. if a[i]>k then break;
  213. p4:=a[i];p3:=a[i+1];
  214. end;
  215. procedure set_memory;
  216. var
  217. i:longint;
  218. begin
  219. m:=n*n;
  220. for i:=1 to m do
  221. new(e_free[i]);
  222. end;
  223. function get_memory:edge;
  224. begin
  225. dec(m);
  226. get_memory:=e_free[m+1];
  227. end;
  228. procedure add_edge(x,y:longint);
  229. var
  230. e:edge;
  231. begin
  232. if way[x,y] then exit;
  233. e:=get_memory;
  234. e^.next:=v[x];
  235. e^.x:=y;
  236. v[x]:=e;
  237. way[x,y]:=true;
  238. end;
  239. function get_dis(a,b:point):double;
  240. begin
  241. get_dis:=sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
  242. end;
  243. procedure del_edge(x,y:longint);
  244. var
  245. ee,e:edge;
  246. begin
  247. way[x,y]:=false;
  248. e:=v[x];
  249. if e^.x=y then v[x]:=e^.next
  250. else begin
  251. while e^.next^.x<>y do e:=e^.next;
  252. ee:=e;
  253. e:=e^.next;
  254. ee^.next:=e^.next
  255. end;
  256. inc(m);
  257. e_free[m]:=e;
  258. end;
  259. function get_three(a,b,c:point):point;
  260. var
  261. p1,p2,p3,p4,p:point;
  262. begin
  263. get_bis(a,b,p1,p2);
  264. get_bis(c,a,p3,p4);
  265. if not get_inter(p1,p2,p3,p4,p) then p.y:=1e100;
  266. get_three:=p;
  267. end;
  268. procedure del_all(a,b,c,pd,l,r:longint);
  269. var
  270. e:edge;
  271. x:longint;
  272. begin
  273. e:=v[a];
  274. while e<>nil do
  275. if (get_sit(p[b],p[c],p[e^.x])*pd<0)and(e^.x<>b)and(get_sit(p[a],p[b],p[e^.x])*pd>0)and(e^.x>=l)and(e^.x<=r) then begin
  276. x:=e^.x;
  277. e:=e^.next;
  278. del_edge(a,x);
  279. del_edge(x,a);
  280. end
  281. else e:=e^.next;
  282. end;
  283. procedure merge(min,mid,max:longint);
  284. var
  285. q3,q4,pd,qq2,qq1,q1,q2:longint;
  286. p1,p2,pp1,pp2,pp:point;
  287. e:edge;
  288. begin
  289. fillchar(used,sizeof(used),0);
  290. get_tang(min,mid,max,q1,q2,q3,q4);
  291. qq1:=0;qq2:=0;
  292. add_edge(q1,q2);
  293. add_edge(q2,q1);
  294. add_edge(q3,q4);
  295. add_edge(q4,q3);
  296. while true do begin
  297. get_bis(p[q1],p[q2],p1,p2);
  298. pd:=0;pp.y:=1e100;
  299. e:=v[q1];
  300. while e<>nil do begin
  301. if (e^.x>=min)and(e^.x<=mid) then pp1:=get_three(p[q1],p[q2],p[e^.x])
  302. else pp1.y:=1e101;
  303. if ((used[q2]=0)or(get_sit(p[q2],p[used[q2]],p[e^.x])<0))and(get_sit(p[q2],p[q1],p[e^.x])<0)and((pp1.y<pp.y)or((pp1.y=pp.y)and(get_dis(pp1,p1)<get_dis(pp,p1)))) then begin
  304. pd:=1;
  305. qq1:=e^.x;
  306. pp:=pp1;
  307. end;
  308. e:=e^.next;
  309. end;
  310. e:=v[q2];
  311. while e<>nil do begin
  312. if e^.x>mid then pp2:=get_three(p[q1],p[q2],p[e^.x])
  313. else pp2.y:=1e101;
  314. if ((used[q1]=0)or(get_sit(p[q1],p[used[q1]],p[e^.x])>0))and(get_sit(p[q1],p[q2],p[e^.x])>0)and((pp2.y<pp.y)or((pp2.y=pp.y)and(get_dis(pp2,p1)<get_dis(pp,p1)))) then begin
  315. pd:=2;
  316. qq2:=e^.x;
  317. pp:=pp2;
  318. end;
  319. e:=e^.next;
  320. end;
  321. if pd=1 then begin
  322. add_edge(qq1,q2);
  323. add_edge(q2,qq1);
  324. del_all(q1,qq1,q2,-1,min,mid);
  325. used[q2]:=qq1;
  326. q1:=qq1;
  327. end
  328. else if pd=2 then begin
  329. add_edge(qq2,q1);
  330. add_edge(q1,qq2);
  331. del_all(q2,qq2,q1,1,mid+1,max);
  332. used[q1]:=qq2;
  333. q2:=qq2;
  334. end
  335. else break;
  336. end;
  337. end;
  338. procedure build_vor(min,max:longint);
  339. var
  340. mid:longint;
  341. begin
  342. if max-min=0 then exit
  343. else if max-min=1 then begin
  344. add_edge(min,max);
  345. add_edge(max,min);
  346. end
  347. else if max-min=2 then
  348. if not oneline(p[min],p[max],p[min],p[min+1]) then begin
  349. add_edge(min,min+1);
  350. add_edge(min,max);
  351. add_edge(min+1,min);
  352. add_edge(max,min);
  353. add_edge(min+1,max);
  354. add_edge(max,min+1);
  355. end
  356. else begin
  357. add_edge(min,min+1);
  358. add_edge(min+1,min);
  359. add_edge(min+1,max);
  360. add_edge(max,min+1);
  361. end
  362. else begin
  363. mid:=(max+min) div 2;
  364. build_vor(min,mid);
  365. build_vor(mid+1,max);
  366. merge(min,mid,max);
  367. end;
  368. end;
  369. function check_circle(q:point;r:double;k:longint):boolean;
  370. var
  371. i:longint;
  372. begin
  373. check_circle:=false;
  374. for i:=1 to n do
  375. if (get_dis(q,p[i])-r<zero) then begin
  376. dec(k);
  377. if k<0 then exit;
  378. end;
  379. check_circle:=true;
  380. end;
  381. procedure main;
  382. var
  383. b,i,c:longint;
  384. ee,e:edge;
  385. qmin,q,ans,p1,p2:point;
  386. rans,r:double;
  387. begin
  388. x:=p[n+3].x;
  389. y:=p[n+4].y;
  390. if n=1 then begin
  391. q:=p[1];
  392. if get_dis(q,p[1])<get_dis(p[1],p[n+1]) then q:=p[n+1];
  393. if get_dis(q,p[1])<get_dis(p[1],p[n+2]) then q:=p[n+2];
  394. if get_dis(q,p[1])<get_dis(p[1],p[n+3]) then q:=p[n+3];
  395. if get_dis(q,p[1])<get_dis(p[1],p[n+4]) then q:=p[n+4];
  396. writeln('The safest point is (',q.x:0:1,', ',q.y:0:1,').');
  397. exit;
  398. end;
  399. m:=0;
  400. for i:=1 to n do begin
  401. e:=v[i];
  402. repeat
  403. if e^.x>i then begin
  404. b:=e^.x;
  405. ee:=v[b];c:=ee^.x;
  406. while ee<>nil do begin
  407. if (get_sit(p[i],p[b],p[c])>0)or((get_sit(p[i],p[b],p[ee^.x])<0)and(get_sit(p[b],p[c],p[ee^.x])<0)and(way[ee^.x,i])) then c:=ee^.x;
  408. ee:=ee^.next;
  409. end;
  410. if way[i,c] then begin
  411. inc(m);
  412. tri[m].a:=p[i];
  413. tri[m].b:=p[b];
  414. tri[m].c:=p[c];
  415. end;
  416. end;
  417. e:=e^.next;
  418. until e=nil;
  419. end;
  420. rans:=0;
  421. for i:=1 to m do begin
  422. q:=get_three(tri[i].a,tri[i].b,tri[i].c);
  423. r:=get_dis(q,tri[i].a);
  424. if (r>rans)and(r<1e20)and(q.x>=0)and(q.x<=x)and(q.y>=0)and(q.y<=y) then begin
  425. rans:=r;
  426. ans:=q;
  427. end;
  428. end;
  429. get_tang(1,n div 2,n,b,b,b,b);
  430. for i:=1 to tot-1 do begin
  431. r:=0;
  432. get_bis(p[a[i]],p[a[i+1]],p1,p2);
  433. get_inter(p1,p2,p[n+1],p[n+3],q);
  434. if (get_dis(q,p[a[i]])>r)and(q.x>=0)and(q.x<=x)and(check_circle(q,get_dis(q,p[a[i]]),2)) then begin
  435. qmin:=q;
  436. r:=get_dis(q,p[a[i]]);
  437. end;
  438. get_inter(p1,p2,p[n+3],p[n+4],q);
  439. if (get_dis(q,p[a[i]])>r)and(q.y>=0)and(q.y<=y)and(check_circle(q,get_dis(q,p[a[i]]),2)) then begin
  440. qmin:=q;
  441. r:=get_dis(q,p[a[i]]);
  442. end;
  443. get_inter(p1,p2,p[n+1],p[n+2],q);
  444. if (get_dis(q,p[a[i]])>r)and(q.y>=0)and(q.y<=y)and(check_circle(q,get_dis(q,p[a[i]]),2)) then begin
  445. qmin:=q;
  446. r:=get_dis(q,p[a[i]]);
  447. end;
  448. get_inter(p1,p2,p[n+2],p[n+4],q);
  449. if (get_dis(q,p[a[i]])>r)and(q.x>=0)and(q.x<=x)and(check_circle(q,get_dis(q,p[a[i]]),2)) then begin
  450. qmin:=q;
  451. r:=get_dis(q,p[a[i]]);
  452. end;
  453. if (r>rans)and(r<=1e20) then begin
  454. ans:=qmin;
  455. rans:=r;
  456. end;
  457. end;
  458. { q.x:=x;q.y:=y;r:=1e100;
  459. for i:=1 to n do
  460. if get_dis(p[i],q)<r then
  461. r:=get_dis(p[i],q);
  462. if (r<1e20)and(r>rans) then begin
  463. rans:=r;
  464. ans:=q;
  465. end;
  466. q.x:=0;q.y:=y;r:=1e100;
  467. for i:=1 to n do
  468. if get_dis(p[i],q)<r then
  469. r:=get_dis(p[i],q);
  470. if (r<1e20)and(r>rans) then begin
  471. rans:=r;
  472. ans:=q;
  473. end;
  474. q.x:=x;q.y:=0;r:=1e100;
  475. for i:=1 to n do
  476. if get_dis(p[i],q)<r then
  477. r:=get_dis(p[i],q);
  478. if (r<1e20)and(r>rans) then begin
  479. rans:=r;
  480. ans:=q;
  481. end;
  482. q.x:=0;q.y:=0;r:=1e100;
  483. for i:=1 to n do
  484. if get_dis(p[i],q)<r then
  485. r:=get_dis(p[i],q);
  486. if (r<1e20)and(r>rans) then begin
  487. rans:=r;
  488. ans:=q;
  489. end;}
  490. writeln('The safest point is (',ans.x:0:1,', ',ans.y:0:1,').');
  491. end;
  492. begin
  493. assign(input,'away.in');reset(input);
  494. assign(output,'2009.out');rewrite(output);
  495. while not eof(input) do begin
  496. readln(tasks);
  497. while tasks>0 do begin
  498. dec(tasks);
  499. fill;
  500. init;
  501. if n>1 then begin
  502. set_memory;
  503. build_vor(1,n);
  504. end;
  505. main;
  506. end;
  507. end;
  508. close(input);close(output);
  509. end.