API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jan 18th, 2017
98
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 29.80 KB | None | 0 0
raw download clone embed print report
  1. import java.io.*;
  2. import java.security.*;
  3. import java.util.*;
  4.  
  5.  
  6. class Wall {
  7. public P start, end;
  8. public long minx, miny;
  9. public long maxx, maxy;
  10. public Wall(P st, P e) {
  11. start = st;
  12. end = e;
  13. minx = st.x < e.x ? st.x : e.x;
  14. maxx = st.x > e.x ? st.x : e.x;
  15. miny = st.y < e.y ? st.y : e.y;
  16. maxy = st.y > e.y ? st.y : e.y;
  17. }
  18. public String toString() {
  19. return "[" + start + " - " + end + "]";
  20. }
  21. // check whether a-b segment intersects c-d segment (1-dimension)
  22. public static boolean boundBoxIntersect(long a, long b, long c, long d) {
  23. return Math.max(Math.min(a, b), Math.min(c, d)) <=
  24. Math.min(Math.max(a, b), Math.max(c, d));
  25. }
  26. // calculate oriented area of ABC triangle
  27. private static long orientedAreaSign(P a, P b, P c) {
  28. long area = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
  29. return area == 0 ? 0 : area / Math.abs(area);
  30. }
  31. public boolean intersect(Wall other) {
  32. // two segments intersect if 1) their bounding boxes intersect and 2) oriented areas of triangles have different signs
  33. return
  34. //boundBoxIntersect(start.x, end.x, other.start.x, other.end.x) &&
  35. //boundBoxIntersect(start.y, end.y, other.start.y, other.end.y) &&
  36. Math.max(minx, other.minx) <= Math.min(maxx, other.maxx) &&
  37. Math.max(miny, other.miny) <= Math.min(maxy, other.maxy) &&
  38. orientedAreaSign(start, end, other.start) * orientedAreaSign(start, end, other.end) <= 0 &&
  39. orientedAreaSign(other.start, other.end, start) * orientedAreaSign(other.start, other.end, end) <= 0;
  40. }
  41. }
  42.  
  43. // the lights can only be placed in lattice points 0.00, 0.01, ..., 0.99, 1.00
  44. // illumination is checked in points between lattice points 0.005, 0.015, ...
  45. class P {
  46. public static final double eps = 1E-6;
  47. public static final int f = 100;// the number of parts we divide each unit of length into
  48. public long x, y;
  49. private double xd, yd;
  50. public boolean hasConverted = false;
  51. public P() {};
  52. public P(long x1, long y1) {
  53. x = x1;
  54. y = y1;
  55. }
  56. private long P2(long a) {
  57. return a * a;
  58. }
  59. public long dist2(P other) {
  60. return P2(x - other.x) + P2(y - other.y);
  61. }
  62. // to define whether the point is within lighting radius of the light
  63. public boolean near(P other, long d) {
  64. return dist2(other) <= P2(2 * d * f);
  65. }
  66. public String toString() {
  67. if(!hasConverted) {
  68. xd = x / 2.0 / f;
  69. yd = y / 2.0 / f;
  70. hasConverted = true;
  71. }
  72. return "(" + xd + "," + yd + ")";
  73. }
  74. }
  75.  
  76. class Map {
  77. String[] map;
  78. int S;
  79. int D;
  80. int L;
  81. ArrayList<Wall> walls;
  82. ArrayList<ArrayList<Wall>> nearbyWalls;
  83. Map(String[] map, int S, int D, int L) {
  84. this.map = map;
  85. this.S = S;
  86. this.D = D;
  87. this.L = L;
  88. this.walls = extractWalls();
  89. this.nearbyWalls = new ArrayList<ArrayList<Wall>>();
  90.  
  91. for(int r=0; r < S; r++) {
  92. for(int c=0; c < S; c++) {
  93. ArrayList<Wall> nearby = new ArrayList<Wall>();
  94. for (int i = 0; i < walls.size(); ++i) {
  95. int boxX1 = Math.max(1, c*P.f*2 + 1 - D*P.f*2);
  96. int boxX2 = Math.min(S*P.f*2-1, c*P.f*2 + P.f*2 -1 + D*P.f*2);
  97. int boxY1 = Math.max(1, r*P.f*2 + 1 - D*P.f*2);
  98. int boxY2 = Math.min(S*P.f*2-1, r*P.f*2 + P.f*2 -1 + D*P.f*2);
  99. Wall w =walls.get(i);
  100. if (Wall.boundBoxIntersect(boxX1, boxX2, w.start.x, w.end.x) &&
  101. Wall.boundBoxIntersect(boxY1, boxY2, w.start.y, w.end.y)) {
  102. nearby.add(w);
  103. }
  104. }
  105. //System.err.println("Putting " + (r*S+c));
  106. nearbyWalls.add(nearby);
  107. //System.err.println("Putting2 " + (nearbyWalls.get(r*S+c)));
  108. }
  109. }
  110. }
  111. boolean isWall(int y, int x) {
  112. return map[y].charAt(x) == '#';
  113. }
  114. ArrayList<Wall> getNearbyWalls(P p) {
  115. //System.err.println("Getting1 " + nearbyWalls);
  116. int g = (int) ((p.y / (P.f*2)) * S + (p.x / (P.f*2)));
  117. //System.err.println("Getting " + ((p.y / (P.f*2)) * S + (p.x / (P.f*2))));
  118. ArrayList<Wall> ret = nearbyWalls.get(g);
  119. if(ret == null) {
  120. System.err.println("invalid point p=" + p);
  121. }
  122. return ret;
  123. }
  124. ArrayList<Wall> extractWalls() {
  125. ArrayList<Wall> walls = new ArrayList<>();
  126. // we don't need outer walls (walls between map and outside of the map), since all light it within the map
  127. // a wall is a vertical or horizontal line which on each 1-length piece is bordered by both wall and empty space
  128. // horizontal walls
  129. for (int i = 0; i < S - 1; ++i) {
  130. int j = 0;
  131. while (j < S) {
  132. // check whether j is start of the wall
  133. if (map[i].charAt(j) == map[i+1].charAt(j)) {
  134. j++;
  135. continue;
  136. }
  137. // if it is, keep increasing it until the wall ends
  138. P start = new P(j * 2 * P.f, (i+1) * 2 * P.f);
  139. while (j < S && map[i].charAt(j) != map[i+1].charAt(j)) {
  140. j++;
  141. }
  142. P end = new P(j * 2 * P.f, (i+1) * 2 * P.f);
  143. Wall w = new Wall(start, end);
  144. walls.add(w);
  145. }
  146. }
  147.  
  148. // vertical walls
  149. for (int j = 0; j < S - 1; ++j) {
  150. int i = 0;
  151. while (i < S) {
  152. // check whether j is start of the wall
  153. if (map[i].charAt(j) == map[i].charAt(j+1)) {
  154. i++;
  155. continue;
  156. }
  157. // if it is, keep increasing it until the wall ends
  158. P start = new P((j+1) * 2 * P.f, i * 2 * P.f);
  159. while (i < S && map[i].charAt(j) != map[i].charAt(j+1)) {
  160. i++;
  161. }
  162. P end = new P((j+1) * 2 * P.f, i * 2 * P.f);
  163. Wall w = new Wall(start, end);
  164. walls.add(w);
  165. }
  166. }
  167. return walls;
  168. }
  169. }
  170.  
  171. class Scene {
  172. int S;
  173. Map map;
  174. int D;
  175. int L;
  176. long startTime = System.currentTimeMillis();
  177. P[] lights = new P[L];
  178. P[] maxLights = new P[L];
  179. int[] lightContrib = new int[L];
  180. int[] lightContribWoOverlap = new int[L];
  181. int[] maxLightContrib = new int[L];
  182. int[] maxLightContribWoOverlap = new int[L];
  183. int maxScore;
  184. int tries = 0;
  185. int subdiv;
  186. int[][] points = new int[S * subdiv][S * subdiv];
  187. int[][] maxPoints = new int[S * subdiv][S * subdiv];
  188. int nTotal;
  189. P[][] pointsLoc;
  190. int lastLightMoved = -1;
  191. int score;
  192.  
  193. Scene(){}
  194.  
  195. void init(Map map, int S, int D, int L, int subdivPoints) {
  196. this.S = S;
  197. this.map = map;
  198. this.D = D;
  199. this.L = L;
  200.  
  201. System.err.println("S = " + S);
  202. System.err.println("D = " + D);
  203. System.err.println("L = " + L);
  204.  
  205. lights = new P[L];
  206. maxLights = new P[L];
  207. lightContrib = new int[L];
  208. lightContribWoOverlap = new int[L];
  209. maxLightContrib = new int[L];
  210. maxLightContribWoOverlap = new int[L];
  211.  
  212. incSubdiv(subdivPoints);
  213.  
  214. points = new int[S * subdiv][S * subdiv];
  215. maxPoints = new int[S * subdiv][S * subdiv];
  216. pointsLoc = new P[S * subdiv][S * subdiv];
  217. for(int y=0; y < S * subdiv; y++) {
  218. for(int x=0; x < S * subdiv; x++) {
  219. pointsLoc[y][x] = new P(x * P.f * 2 / subdiv + P.f / subdiv, y * P.f * 2 / subdiv + P.f / subdiv);
  220. }
  221. }
  222. nTotal = getFloorPoints();
  223. markWallPoints();
  224. }
  225.  
  226. void incSubdiv(int maxSamplePoints) {
  227. int oldsubdiv = subdiv;
  228.  
  229. subdiv = (int)Math.sqrt(maxSamplePoints / (S*S));
  230. if(subdiv >= 100) {
  231. subdiv = 100;
  232. } else if(subdiv >= 50) {
  233. subdiv = 50;
  234. } else if(subdiv >= 25) {
  235. subdiv = 25;
  236. } else if(subdiv >= 20) {
  237. subdiv = 20;
  238. } else if(subdiv >= 10) {
  239. subdiv = 10;
  240. } else if(subdiv >= 5) {
  241. subdiv = 5;
  242. } else if(subdiv >= 4) {
  243. subdiv = 4;
  244. } else if(subdiv >= 2) {
  245. subdiv = 2;
  246. } else {
  247. subdiv = 1;
  248. }
  249. // Don't ever decrease
  250. if(subdiv <= oldsubdiv) {
  251. subdiv = oldsubdiv;
  252. return;
  253. }
  254.  
  255. points = new int[S * subdiv][S * subdiv];
  256. maxPoints = new int[S * subdiv][S * subdiv];
  257. pointsLoc = new P[S * subdiv][S * subdiv];
  258. for(int y=0; y < S * subdiv; y++) {
  259. for(int x=0; x < S * subdiv; x++) {
  260. pointsLoc[y][x] = new P(x * P.f * 2 / subdiv + P.f / subdiv, y * P.f * 2 / subdiv + P.f / subdiv);
  261. }
  262. }
  263. clearLights();
  264. addLights();
  265. maxScore=illuminatedPoints();
  266. nTotal = getFloorPoints();
  267. markWallPoints();
  268. save();
  269.  
  270. if(subdiv != oldsubdiv) System.err.println("setting subdiv to " + subdiv);
  271. }
  272.  
  273. void markWallPoints() {
  274. // mark wall points beforehand
  275. for (int r = 0; r < S; ++r)
  276. for (int c = 0; c < S; ++c) {
  277. if (!map.isWall(r, c))
  278. continue;
  279. for (int x = c * subdiv; x < (c + 1) * subdiv; ++x)
  280. for (int y = r * subdiv; y < (r + 1) * subdiv; ++y) {
  281. points[y][x] = -1;
  282. }
  283. }
  284. //System.err.println("Done marking walls");
  285. }
  286.  
  287. void clearPoints() {
  288. for (int r = 0; r < S * subdiv; ++r) {
  289. for (int c = 0; c < S * subdiv; ++c) {
  290. if(points[r][c] != -1) points[r][c] = 0;
  291. }
  292. }
  293. }
  294. void clearLight(int lightIdx) {
  295. P light = lights[lightIdx];
  296. if(light == null) return;
  297. long boxX1 = Math.max(0, light.x - 2 * P.f * D);
  298. long boxX2 = Math.min(2 * (P.f * S - 1), light.x + 2 * P.f * D);
  299. long boxY1 = Math.max(0, light.y - 2 * P.f * D);
  300. long boxY2 = Math.min(2 * (P.f * S - 1), light.y + 2 * P.f * D);
  301. for (int y = (int)boxY1 * subdiv / P.f / 2; y <= boxY2 * subdiv / P.f / 2; ++y)
  302. for (int x = (int)boxX1 * subdiv / P.f / 2; x <= boxX2 * subdiv / P.f / 2; ++x) {
  303. if(points[y][x] != -1 && (points[y][x] & (1<<lightIdx)) != 0) {
  304. points[y][x] &= ~(1<<lightIdx);
  305. }
  306. }
  307. lightContrib[lightIdx] = 0;
  308. lightContribWoOverlap[lightIdx] = 0;
  309. // for (int r = 0; r < S * subdiv; ++r) {
  310. // for (int c = 0; c < S * subdiv; ++c) {
  311. // if(points[r][c] != -1 && (points[r][c] & (1<<lightIdx)) != 0) {
  312. // points[r][c] &= ~(1<<lightIdx);
  313. // }
  314. // }
  315. // }
  316. }
  317. void clearLights() {
  318. for (int r = 0; r < S * subdiv; ++r) {
  319. for (int c = 0; c < S * subdiv; ++c) {
  320. if(points[r][c] != -1) {
  321. points[r][c] = 0;
  322. }
  323. }
  324. }
  325. for(int l=0; l < L; l++) {
  326. lightContrib[l] = 0;
  327. lightContribWoOverlap[l] = 0;
  328. }
  329. }
  330. int getFloorPoints() {
  331. int nIllum = 0, nTotal = 0;
  332. for (int r = 0; r < S; ++r)
  333. for (int c = 0; c < S; ++c) {
  334. if (map.isWall(r, c))
  335. continue;
  336. nTotal += subdiv * subdiv;
  337. }
  338. return nTotal;
  339. }
  340. int illuminatedPoints() {
  341. //System.err.println("Done lighting. Counting points...");
  342. // check all points within the map and count illuminated ones
  343.  
  344. int nIllum = 0, nTotal = 0;
  345. for (int r = 0; r < S; ++r)
  346. for (int c = 0; c < S; ++c) {
  347. if (map.isWall(r, c))
  348. continue;
  349. for (int x = 0; x < subdiv; ++x)
  350. for (int y = 0; y < subdiv; ++y) {
  351. // the point we need to check is middle of square of size 1/P.f
  352. nTotal++;
  353. if (points[r * subdiv + y][c * subdiv + x] > 0)
  354. nIllum++;
  355. }
  356. }
  357.  
  358. // int nIllum2 = 0;
  359. // for(int l=0; l < L; l++) {
  360. // nIllum2 += lightContribWoOverlap[l];
  361. // }
  362. score = nIllum;
  363. return score;
  364. }
  365.  
  366. void addLights() {
  367. for(int lightIdx = 0; lightIdx < lights.length; lightIdx++) {
  368. addLight(lightIdx);
  369. }
  370. }
  371.  
  372. boolean isPointLitByLight(ArrayList<Wall> localWalls, int lightIdx, P point) {
  373. P light = lights[lightIdx];
  374. return isPointLitByLight(localWalls, light, point);
  375. }
  376. boolean isPointLitByLight(ArrayList<Wall> localWalls, P light, P point) {
  377. if (!light.near(point, D))
  378. return false;
  379. Wall beam = new Wall(point, light);
  380. for (int i=0; i < localWalls.size(); i++) {
  381. //if (beam.intersect(walls.get(ind))) {
  382. if (localWalls.get(i).intersect(beam)) {
  383. return false;
  384. }
  385. }
  386. return true;
  387. }
  388. boolean isPointLitByLightInefficient(P light, P point) {
  389. // first, find bounding box of the light and only get the walls which intersect it
  390. long boxX1 = Math.max(0, light.x - 2 * P.f * D);
  391. long boxX2 = Math.min(2 * (P.f * S - 1), light.x + 2 * P.f * D);
  392. long boxY1 = Math.max(0, light.y - 2 * P.f * D);
  393. long boxY2 = Math.min(2 * (P.f * S - 1), light.y + 2 * P.f * D);
  394.  
  395. ArrayList<Wall> walls = map.getNearbyWalls(light);
  396. return isPointLitByLight(walls, light, point);
  397. }
  398. void addLightInCell(ArrayList<Wall> localWalls, int lightIdx, int x1, int y1, int x2, int y2) {
  399. if(x2 - x1 <= 2 || y2 - y1 <= 2) {
  400. for(int y=y1; y < y2; y++) {
  401. for(int x=x1; x < x2; x++) {
  402. P point = new P(x * P.f * 2 / subdiv + P.f / subdiv, y * P.f * 2 / subdiv + P.f / subdiv);
  403. if(isPointLitByLight(localWalls, lightIdx, point)){
  404. if(points[y][x] == 0) {
  405. lightContribWoOverlap[lightIdx]++;
  406. }
  407. points[y][x] |= (1 << lightIdx);
  408. lightContrib[lightIdx]++;
  409. }
  410. }
  411. }
  412. return;
  413. }
  414.  
  415.  
  416. long mul = P.f * 2 / subdiv;
  417. long add = P.f / subdiv;
  418. //new P(x * P.f * 2 / subdiv + P.f / subdiv, y * P.f * 2 / subdiv + P.f / subdiv);
  419. P tl = new P(x1 * mul + add, y1 * mul + add);
  420. P tr = new P(x2 * mul + add, y1 * mul + add);
  421. P bl = new P(x1 * mul + add, y2 * mul + add);
  422. P br = new P(x2 * mul + add, y2 * mul + add);
  423. boolean tlLit = isPointLitByLight(localWalls, lightIdx, tl);
  424. boolean trLit = isPointLitByLight(localWalls, lightIdx, tr);
  425. boolean blLit = isPointLitByLight(localWalls, lightIdx, bl);
  426. boolean brLit = isPointLitByLight(localWalls, lightIdx, br);
  427. if(tlLit && trLit && blLit && brLit) {
  428. //System.err.printf("Whole square (%d %d) (%d %d)%n", x1, y1, x2, y2);
  429. for(int y=y1; y < y2; y++) {
  430. for(int x=x1; x < x2; x++) {
  431. if(points[y][x] == 0) {
  432. lightContribWoOverlap[lightIdx]++;
  433. }
  434. points[y][x] |= (1 << lightIdx);
  435. lightContrib[lightIdx]++;
  436. }
  437. }
  438. return;
  439. }
  440.  
  441. for(int y=y1; y < y2; y++) {
  442. for(int x=x1; x < x2; x++) {
  443. P point = pointsLoc[y][x];
  444. if(isPointLitByLight(localWalls, lightIdx, point)){
  445. if(points[y][x] == 0) {
  446. lightContribWoOverlap[lightIdx]++;
  447. }
  448. points[y][x] |= (1 << lightIdx);
  449. lightContrib[lightIdx]++;
  450. }
  451. }
  452. }
  453. }
  454.  
  455. void addLight(int lightIdx) {
  456. P light = lights[lightIdx];
  457. if(light == null) return;
  458. // first, find bounding box of the light and only get the walls which intersect it
  459. long boxX1 = Math.max(0, light.x - 2 * P.f * D);
  460. long boxX2 = Math.min(2 * (P.f * S - 1), light.x + 2 * P.f * D);
  461. long boxY1 = Math.max(0, light.y - 2 * P.f * D);
  462. long boxY2 = Math.min(2 * (P.f * S - 1), light.y + 2 * P.f * D);
  463.  
  464.  
  465. //System.err.println("Doing light #" + lightIdx);
  466. // now iterate throw points in the bounding box and see whether they are illuminated
  467. // using only local walls, not the whole list
  468. //
  469. // the far bound could be optimized, <= might not be needed
  470. // ArrayList<Wall> walls = map.getNearbyWalls(light);
  471. // for(int c=(int)(boxX1 / (P.f*2)); c < (boxX2 + P.f*2 - 1) / (P.f*2); c++) {
  472. // for(int r=(int)(boxY1 / (P.f*2)); r < (boxY2 + P.f*2 - 1) / (P.f*2); r++) {
  473. // ArrayList<Wall> walls2 = map.getNearbyWalls(light);
  474. // addLightInCell(walls, lightIdx,
  475. // c * subdiv,
  476. // r * subdiv,
  477. // (c+1) * subdiv,
  478. // (r+1) * subdiv);
  479. // }
  480. // }
  481.  
  482. for (int y = (int)boxY1 * subdiv / P.f / 2; y <= boxY2 * subdiv / P.f / 2; ++y)
  483. for (int x = (int)boxX1 * subdiv / P.f / 2; x <= boxX2 * subdiv / P.f / 2; ++x) {
  484.  
  485. if (points[y][x] == -1) {
  486. // point is part of a wall
  487. continue;
  488. }
  489.  
  490. P point = pointsLoc[y][x];
  491. boolean lit = isPointLitByLightInefficient(light, point);
  492. if (lit) {
  493. if(points[y][x] == 0) {
  494. lightContribWoOverlap[lightIdx]++;
  495. }
  496. points[y][x] |= (1 << lightIdx);
  497. lightContrib[lightIdx]++;
  498. }
  499. }
  500. lastLightMoved = lightIdx;
  501. //System.err.println("Light #" + lightIdx + " is " + lightContribWoOverlap[lightIdx]);
  502. }
  503. void save() {
  504. // System.err.println("Save");
  505. maxScore = score;
  506. System.arraycopy(lights, 0, maxLights,0, L);
  507. for(int r=0; r < S*subdiv; r++) System.arraycopy(points[r],0,maxPoints[r],0,S*subdiv);
  508. System.arraycopy(lightContrib,0,maxLightContrib,0,L);
  509. System.arraycopy(lightContribWoOverlap,0,maxLightContribWoOverlap,0,L);
  510. }
  511. void restore() {
  512. // System.err.println("Restore");
  513. score = maxScore;
  514. lights = maxLights.clone();
  515. System.arraycopy(maxLights, 0, lights,0, L);
  516. for(int r=0; r < S*subdiv; r++) System.arraycopy(maxPoints[r],0,points[r],0,S*subdiv);
  517. System.arraycopy(maxLightContrib,0,lightContrib,0,L);
  518. System.arraycopy(maxLightContribWoOverlap,0,lightContribWoOverlap,0,L);
  519. }
  520. int getLeastContribLight() {
  521. int lightIdx=0;
  522. int minContrib=lightContrib[0];
  523. for(int l=0; l< L; l++) {
  524. if(lightContrib[l] < minContrib) {
  525. lightIdx = l;
  526. minContrib = lightContrib[l];
  527. }
  528. }
  529. return lightIdx;
  530. }
  531. int getLeastContribLightWoOverlap() {
  532. int lightIdx=0;
  533. int minContrib=lightContribWoOverlap[0];
  534. for(int l=0; l< L; l++) {
  535. if(lightContribWoOverlap[l] < minContrib) {
  536. lightIdx = l;
  537. minContrib = lightContribWoOverlap[l];
  538. }
  539. }
  540. return lightIdx;
  541. }
  542. P randLight(Random r) {
  543. int xw, xdec, yw, ydec;
  544. P light = new P();
  545. do {
  546. xw = r.nextInt(S);
  547. xdec = r.nextInt(P.f);
  548. yw = r.nextInt(S);
  549. ydec = r.nextInt(P.f);
  550.  
  551. if(map.isWall(yw, xw)) continue;
  552. if(xdec == 0) {
  553. if(xw > 0) {
  554. if(map.isWall(yw, xw-1)) continue;
  555. } else {
  556. continue;
  557. }
  558. }
  559. if(ydec == 0) {
  560. if(yw > 0) {
  561. if(map.isWall(yw-1, xw)) continue;
  562. } else {
  563. continue;
  564. }
  565. }
  566. break;
  567. } while(true);
  568. return new P(xw*2*P.f + xdec*2, yw*2*P.f + ydec*2);
  569. }
  570. void moveLightToRand(Random r, int lightIdx) {
  571. clearLight(lightIdx);
  572. lights[lightIdx] = randLight(r);
  573. addLight(lightIdx);
  574. }
  575. boolean isLightValid(P light) {
  576. if(light.x <= 0) return false;
  577. if(light.y <= 0) return false;
  578. if(light.x >= P.f*2*S) return false;
  579. if(light.y >= P.f*2*S) return false;
  580. int xw = (int) (light.x/(2*P.f));
  581. int xdec = (int) (light.x%(2*P.f));
  582. int yw = (int) (light.y/(2*P.f));
  583. int ydec = (int) (light.y%(2*P.f));
  584.  
  585. if(map.isWall(yw,xw)) return false;
  586. if(xdec == 0) {
  587. if(xw > 0) {
  588. if(map.isWall(yw,xw-1)) return false;
  589. } else {
  590. return false;
  591. }
  592. }
  593. if(ydec == 0) {
  594. if(yw > 0) {
  595. if(map.isWall(yw-1,xw)) return false;
  596. } else {
  597. return false;
  598. }
  599. }
  600. return true;
  601. }
  602. boolean tieBreakMax(Random r) {
  603. long count=0;
  604. long maxCount=0;
  605.  
  606. // for(int i=0; i < 500; i++) {
  607. // P p = randLight(r);
  608. // boolean lit=false, litMax = false;
  609. // for(int l=0; l < L; l++) {
  610. // if(!lit) lit = isPointLitByLightInefficient(lights[l], p);
  611. // if(!litMax) litMax = isPointLitByLightInefficient(maxLights[l], p);
  612. // }
  613. // if(lit) count++;
  614. // if(litMax) maxCount++;
  615. // if(count > maxCount){
  616. // System.err.println("TIE BREAKKKEERRR " + count + ", " + maxCount);
  617. // return true;
  618. // }
  619. // if(maxCount < count) return false;
  620.  
  621. // for(int y=0; y < S; y++) {
  622. // for(int x=0; x < S; x++) {
  623. // if(!map.isWall(y,x)) {
  624. // P[] ps = new P[4];
  625. // ps[0] = new P(x*P.f*2 + 1, y*P.f*2 + 1);
  626. // ps[1] = new P(x*P.f*2 + P.f*2 -1, y*P.f*2 + 1);
  627. // ps[2] = new P(x*P.f*2 + 1, y*P.f*2 + P.f*2 -1);
  628. // ps[3] = new P(x*P.f*2 + P.f*2 -1, y*P.f*2 + P.f*2 -1);
  629. // boolean[] lit = new boolean[4];
  630. // boolean[] mlit = new boolean[4];
  631. // for(int pnum=0; pnum < 4; pnum++) {
  632. // for(int l=0; l < L; l++) {
  633. // if(!lit[pnum] && isPointLitByLightInefficient(lights[l], ps[pnum])) {
  634. // count++;
  635. // lit[pnum]=true;
  636. // }
  637. // if(!mlit[pnum] && isPointLitByLightInefficient(maxLights[l], ps[pnum])) {
  638. // maxCount++;
  639. // mlit[pnum]=true;
  640. // }
  641. // }
  642. // }
  643. // }
  644. // }
  645. // }
  646. //
  647. // if(count > maxCount){
  648. // System.err.println("TIE BREAKKKEERRR " + count + ", " + maxCount);
  649. // return true;
  650. // }
  651. // if(maxCount < count) return false;
  652.  
  653. return true;
  654. }
  655. }
  656.  
  657.  
  658. public class Lighting {
  659.  
  660. String[] setLights(String[] mapStrings, int D, int L) {
  661. String[] ret = new String[L];
  662. // place L random valid lights
  663. Random r1;
  664. try {
  665. r1 = new Random();
  666. } catch (Exception e) { return ret; }
  667. r1.setSeed(123);
  668. int S = mapStrings.length;
  669. /*
  670. System.err.println("S = " + S);
  671. System.err.println("L = " + L);
  672. long maxScore = 0;
  673. P[] lights = new P[L];
  674. P[] maxLights = new P[L];
  675. int[] lightContrib = new int[L];
  676. int[] lightContribWoOverlap = new int[L];
  677. int[] maxLightContrib = new int[L];
  678. int[] maxLightContribWoOverlap = new int[L];
  679. ArrayList<Wall> walls = extractWalls(map);
  680. */
  681. final int NUM_SCENES = 2500/(S*S);
  682. final long MILLIS_TO_RUN = 19500;
  683. long startTime = System.currentTimeMillis();
  684. int tries = 0;
  685. boolean uppedres1 = false, uppedres2 = false;
  686.  
  687. Map map = new Map(mapStrings, S, D, L);
  688.  
  689. ArrayList<Scene> scenes = new ArrayList<Scene>();
  690. int nTotal;
  691. for(int i=0; i < NUM_SCENES; i++) {
  692. Scene scene = new Scene();
  693. //scene.init(map, S, D, L, 1);
  694. scene.init(map, S, D, L, 10000);
  695.  
  696. for (int l = 0; l < L; ++l) {
  697. scene.moveLightToRand(r1, l);
  698. }
  699. scene.addLights();
  700. scenes.add(scene);
  701. }
  702. nTotal = scenes.get(0).getFloorPoints();
  703.  
  704. int sceneNum = 0;
  705. while(true) {
  706. Scene scene = scenes.get(sceneNum);
  707. scene.illuminatedPoints();
  708.  
  709. long curTime = System.currentTimeMillis();
  710. long millis = curTime - startTime;
  711. long millisLeft = MILLIS_TO_RUN - millis;
  712. if(millisLeft <=0) break;
  713.  
  714. tries++;
  715. if(scene.score == nTotal) {
  716. for(Scene s: scenes) s.incSubdiv(200000);
  717. nTotal = scenes.get(0).getFloorPoints();
  718. scene.save();
  719. }
  720. // System.err.println("blah! #" + sceneNum + " score=" + scene.score);
  721. if(scene.score > scene.maxScore) {
  722. System.err.println("success! #" + sceneNum + " score=" + (scene.score*1.0/nTotal));
  723. scene.save();
  724. } else if(scene.score == scene.maxScore) {
  725. if(scene.tieBreakMax(r1)) {
  726. //System.err.println("TIE BREAKKKEERRR");
  727. //System.err.println("tie. #" + sceneNum + " score=" + (scene.score*1.0/nTotal));
  728. scene.save();
  729. } else {
  730. //System.err.println("Tie breaker fail");
  731. scene.restore();
  732. }
  733. } else {
  734. //System.err.println("worse #" + sceneNum + " score=" + (scene.score*1.0/nTotal));
  735. scene.restore();
  736. }
  737.  
  738.  
  739. // if(!uppedres1 && millisLeft <= 2000) {
  740. // uppedres1 = true;
  741. // for(Scene s: scenes) s.incSubdiv(100000);
  742. // nTotal = scenes.get(0).getFloorPoints();
  743. // }
  744.  
  745. for(Scene s: scenes) s.incSubdiv((int)(millis * 2));
  746. nTotal = scenes.get(0).getFloorPoints();
  747.  
  748.  
  749. if(tries%10000 == 0 && scenes.size() > 1) {
  750. Scene minScene = null;
  751. long minScore = Long.MAX_VALUE;
  752. Scene maxScene = null;
  753. long maxScore = 0;
  754. int minSn = 0;
  755. for (int sn=0; sn < scenes.size(); sn++) {
  756. Scene s = scenes.get(sn);
  757. if(s.score < minScore) {
  758. minSn = sn;
  759. minScene = s;
  760. minScore = s.score;
  761. }
  762. if(s.score > maxScore) {
  763. maxScene = s;
  764. maxScore = s.score;
  765. }
  766. }
  767. if(maxScene != minScene) {
  768. for(int l=0; l < L; l++) {
  769. minScene.lights[l] = new P(maxScene.lights[l].x, maxScene.lights[l].y);
  770. }
  771. minScene.lights[r1.nextInt(L)] = minScene.randLight(r1);
  772. minScene.clearLights();
  773. minScene.addLights();
  774. minScene.maxScore = minScene.illuminatedPoints();
  775. //System.err.println("Fixing #" + minSn);
  776. }
  777. }
  778.  
  779. // Remove worst one
  780. long m = Math.max(millisLeft-2000, 0);
  781. while(scenes.size() > (m / 1000)*(m / 1000)*(m/1000) + 1) {
  782. Scene minScene = null;
  783. long minScore = Long.MAX_VALUE;
  784. for (Scene s: scenes) {
  785. if(s.score < minScore) {
  786. minScene = s;
  787. minScore = s.score;
  788. }
  789. }
  790. scenes.remove(minScene);
  791. if(sceneNum >= scenes.size()) sceneNum = 0;
  792. }
  793.  
  794. if(millis <= 10*1000) {
  795. int choice = r1.nextInt(10);
  796. //choice = 2;
  797. if(choice == 0) {
  798. // move least contrib light (counting overlap)
  799. int lightIdx = scene.getLeastContribLight();
  800. scene.moveLightToRand(r1, lightIdx);
  801. } else if(choice == -1) {
  802. // move least contrib light (not counting overlap)
  803. int lightIdx = scene.getLeastContribLightWoOverlap();
  804. scene.moveLightToRand(r1, lightIdx);
  805. } else {
  806. // move random light
  807. int lightIdx = r1.nextInt(L);
  808. scene.moveLightToRand(r1, lightIdx);
  809. }
  810. } else {
  811. // move random light a tiny amount
  812. //System.err.println("jiggling...");
  813. int lightIdx = r1.nextInt(L);
  814. long amtx=0, amty=0;
  815.  
  816. while(true) {
  817. do {
  818. //amtx=(r1.nextInt(P.f*2/scene.subdiv + 1)-P.f/scene.subdiv)*2;
  819. //amty=(r1.nextInt(P.f*2/scene.subdiv + 1)-P.f/scene.subdiv)*2;
  820. long maxMove = P.f*2 * S / 2;
  821. //maxMove = maxMove * millisLeft / MILLIS_TO_RUN + 1;
  822. //maxMove = maxMove * millisLeft / MILLIS_TO_RUN * millisLeft / MILLIS_TO_RUN + 1;
  823. long m2 = millisLeft;
  824. maxMove = maxMove * m2 / MILLIS_TO_RUN * m2 / MILLIS_TO_RUN + 11;
  825. //System.err.println("maxmove=" + maxMove);
  826. //maxMove = (long) (maxMove * Math.exp((millisLeft-MILLIS_TO_RUN) / MILLIS_TO_RUN) + P.f*5);
  827. //System.err.println(maxMove + ", " + millisLeft);
  828. amtx=(r1.nextInt((int)maxMove*2 + 1) - maxMove)*2;
  829. amty=(r1.nextInt((int)maxMove*2 + 1) - maxMove)*2;
  830. } while(amtx==0 && amty==0);
  831.  
  832.  
  833. P newLight = new P(scene.lights[lightIdx].x + amtx, scene.lights[lightIdx].y + amty);
  834. if(!scene.isLightValid(newLight)) continue;
  835.  
  836. scene.clearLight(lightIdx);
  837. scene.lights[lightIdx] = newLight;
  838. break;
  839. }
  840.  
  841.  
  842. scene.addLight(lightIdx);
  843.  
  844. }
  845.  
  846. sceneNum++;
  847. if(sceneNum >= scenes.size()) sceneNum = 0;
  848. }
  849.  
  850. Scene scene = null;
  851. long maxScore = Long.MIN_VALUE;
  852. for(Scene s: scenes) {
  853. if(s.maxScore > maxScore) {
  854. scene = s;
  855. maxScore = s.maxScore;
  856. }
  857. }
  858.  
  859. System.err.println("nTotal = " + nTotal);
  860. System.err.println("subdiv = " + scene.subdiv);
  861. System.err.println("tries = " + tries);
  862. for (int i = 0; i < L; ++i) {
  863. long xw = scene.maxLights[i].x/(2*P.f);
  864. long xdec = (scene.maxLights[i].x%(2*P.f))/2;
  865. long yw = scene.maxLights[i].y/(2*P.f);
  866. long ydec = (scene.maxLights[i].y%(2*P.f))/2;
  867. ret[i] = String.format("%d.%02d %d.%02d", xw, xdec, yw, ydec);
  868. System.err.println("final: " + ret[i]);
  869. }
  870. System.err.println("estim = " + (maxScore * 1.0 / nTotal));
  871. return ret;
  872. }
  873.  
  874. // -------8<------- end of solution submitted to the website -------8<-------
  875. public static void main(String[] args) {
  876. try {
  877. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  878.  
  879. int S = Integer.parseInt(br.readLine());
  880. String[] map = new String[S];
  881. for (int i = 0; i < S; ++i) {
  882. map[i] = br.readLine();
  883. }
  884.  
  885. int D = Integer.parseInt(br.readLine());
  886. int L = Integer.parseInt(br.readLine());
  887.  
  888. Lighting l = new Lighting();
  889. String[] ret = l.setLights(map, D, L);
  890.  
  891. System.out.println(ret.length);
  892. for (int i = 0; i < ret.length; ++i) {
  893. System.out.println(ret[i]);
  894. }
  895. }
  896. catch (Exception e) {
  897. e.printStackTrace();
  898. }
  899. }
  900. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!