fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.math.*;
  4. import java.io.*;
  5.  
  6. import static java.lang.Math.*;
  7. import static java.util.Arrays.*;
  8. import static java.util.Collections.*;
  9.  
  10. public class A{
  11. 	Scanner sc=new Scanner(System.in);
  12.  
  13. 	int INF=1<<28;
  14.  
  15. 	// input
  16. 	int width, height, n;
  17. 	int[] ws0, hs0;
  18.  
  19. 	// trial
  20. 	int[] xs, ys;
  21. 	int[] ws, hs;
  22. 	int[] ts, ss;
  23. 	int[] _;
  24. 	boolean[] us;
  25.  
  26. 	int target;
  27.  
  28. 	// best
  29. 	int[] bestXs, bestYs;
  30. 	int[] bestWs, bestHs;
  31. 	boolean[] bestUs;
  32.  
  33. 	// parameters
  34. 	int marginX, marginY;
  35. 	int maxArea;
  36. 	final double alpha=2.2;
  37.  
  38. 	int[] scales;
  39. 	int nScales;
  40. 	int scalesOrder;
  41. 	final int ascending=1, descending=-1;
  42.  
  43. 	int[] dx1, dy1;
  44. 	int[] dx2, dy2;
  45.  
  46. 	Xorshift xorShift;
  47.  
  48. 	final long timeLimit=4800;
  49.  
  50. 	// debug
  51. 	boolean debug=false, lock=false, draw=false;
  52.  
  53. 	long start;
  54.  
  55. 	void run(){
  56. 		start=System.currentTimeMillis();
  57.  
  58. 		width=sc.nextInt();
  59. 		height=sc.nextInt();
  60. 		n=sc.nextInt();
  61. 		ws0=new int[n];
  62. 		hs0=new int[n];
  63. 		for(int i=0; i<n; i++){
  64. 			ws0[i]=sc.nextInt();
  65. 			hs0[i]=sc.nextInt();
  66. 		}
  67. 		Answer a=solve();
  68. 		StringBuilder sb=new StringBuilder();
  69. 		for(int i=0; i<n; i++){
  70. 			// if x1=y1=x2=y2=-10
  71. 			// output "-1.0 -1.0 -1.0 -1.0"
  72. 			sb.append(a.x1[i]/10);
  73. 			sb.append('.');
  74. 			sb.append(a.x1[i]%10);
  75. 			sb.append(' ');
  76. 			sb.append(a.y1[i]/10);
  77. 			sb.append('.');
  78. 			sb.append(a.y1[i]%10);
  79. 			sb.append(' ');
  80. 			sb.append(a.x2[i]/10);
  81. 			sb.append('.');
  82. 			sb.append(a.x2[i]%10);
  83. 			sb.append(' ');
  84. 			sb.append(a.y2[i]/10);
  85. 			sb.append('.');
  86. 			sb.append(a.y2[i]%10);
  87. 			sb.append('\n');
  88. 		}
  89. 		println(sb.toString());
  90. 	}
  91.  
  92. 	void load(Param param){
  93. 		start=System.currentTimeMillis();
  94.  
  95. 		width=param.w;
  96. 		height=param.h;
  97. 		n=param.n;
  98. 		ws0=param.ws.clone();
  99. 		hs0=param.hs.clone();
  100. 	}
  101.  
  102. 	void init(){
  103. 		width*=10;
  104. 		height*=10;
  105.  
  106. 		for(int i=0; i<n; i++){
  107. 			ws0[i]*=10;
  108. 			hs0[i]*=10;
  109. 		}
  110.  
  111. 		xs=new int[n];
  112. 		ys=new int[n];
  113. 		ws=new int[n];
  114. 		hs=new int[n];
  115. 		ts=new int[n];
  116. 		ss=new int[n];
  117. 		_=new int[n];
  118. 		us=new boolean[n];
  119.  
  120. 		bestXs=new int[n];
  121. 		bestYs=new int[n];
  122. 		bestWs=new int[n];
  123. 		bestHs=new int[n];
  124. 		bestUs=new boolean[n];
  125.  
  126. 		xorShift=new Xorshift();
  127. 	}
  128.  
  129. 	Answer solve(){
  130. 		init();
  131. 		draw=true;
  132. 		if(n<=15){
  133. 			solveSmall();
  134. 		}else{
  135. 			solveLarge();
  136. 		}
  137. 		return output();
  138. 	}
  139.  
  140. 	void solveSmall(){
  141. 		int[][] scaless=new int[2][];
  142. 		scaless[0]=new int[]{20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8,
  143. 				7, 6, 5, 4, 3, 2, 1};
  144. 		scaless[1]=new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
  145. 				16, 17, 18, 19, 20};
  146. 		int[] scalesOrders={descending, ascending};
  147. 		int nScaless=scaless.length;
  148.  
  149. 		dx1=new int[]{0};
  150. 		dy1=new int[]{0};
  151. 		dx2=new int[]{0, -1, 0, -1};
  152. 		dy2=new int[]{0, 0, -1, -1};
  153.  
  154. 		int[] maxAreas={width*height/1, width*height/3, width*height/5,
  155. 				width*height/7, width*height/9};
  156. 		int nMaxAreas=maxAreas.length;
  157.  
  158. 		for(int i=0; i<n; i++){
  159. 			_[i]=i;
  160. 		}
  161.  
  162. 		int bestSumScore=-INF;
  163. 		for(int trial=0;; trial++){
  164. 			maxArea=maxAreas[trial%nMaxAreas];
  165. 			scales=scaless[(trial/nMaxAreas)%nScaless];
  166. 			scalesOrder=scalesOrders[(trial/nMaxAreas)%nScaless];
  167. 			nScales=scales.length;
  168.  
  169. 			fill(us, false);
  170.  
  171. 			int sumScore=0;
  172. 			for(int i=0; i<n; i++){
  173. 				target=i;
  174. 				sumScore+=step2();
  175. 			}
  176.  
  177. 			if(sumScore>bestSumScore){
  178. 				bestSumScore=sumScore;
  179. 				updateBest();
  180. 			}
  181.  
  182. 			shuffleSmall(_);
  183.  
  184. 			long end=System.currentTimeMillis();
  185. 			if(end-start>timeLimit){
  186. 				break;
  187. 			}
  188. 		}
  189. 	}
  190.  
  191. 	void solveLarge(){
  192. 		scales=new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  193. 		scalesOrder=ascending;
  194. 		nScales=scales.length;
  195.  
  196. 		dx1=new int[]{0, 0, 0, -1, 1};
  197. 		dy1=new int[]{0, -1, 1, 0, 0};
  198. 		dx2=new int[]{0, -1, 0, -1};
  199. 		dy2=new int[]{0, 0, -1, -1};
  200.  
  201. 		int min=min(width, height);
  202. 		int[] marginXs={min/4, min/5, min/6, width/4, width/5, width/6};
  203. 		int[] marginYs={min/4, min/5, min/6, height/4, height/5, height/6};
  204. 		int nMargin=marginXs.length;
  205.  
  206. 		maxArea=(int)(alpha*width*height/n);
  207.  
  208. 		int bestSumScore=-INF;
  209. 		for(int trial=0;; trial++){
  210. 			for(int k=0; k<nMargin; k++){
  211. 				marginX=marginXs[k];
  212. 				marginY=marginYs[k];
  213.  
  214. 				Pair[] pairs=new Pair[n];
  215. 				for(int i=0; i<n; i++){
  216. 					double w=ws0[i];
  217. 					double h=hs0[i];
  218. 					// n>25
  219. 					if(trial>0&&n>25){
  220. 						w+=xorShift.nextDouble()*width/10;
  221. 						h+=xorShift.nextDouble()*height/10;
  222. 					}
  223. 					pairs[i]=new Pair(i, w/h);
  224. 				}
  225. 				sort(pairs);
  226. 				int index=0;
  227. 				for(int i=0; i<n/2; i++){
  228. 					_[index++]=pairs[i].key;
  229. 					_[index++]=pairs[n-1-i].key;
  230. 				}
  231. 				if(n%2==1){
  232. 					_[index++]=pairs[n/2].key;
  233. 				}
  234.  
  235. 				// n<=25
  236. 				if(trial>0&&n<=25){
  237. 					for(int s=0; s<2; s++){
  238. 						int i=xorShift.nextInt(n);
  239. 						int j=xorShift.nextInt(n);
  240. 						int t=_[i];
  241. 						_[i]=_[j];
  242. 						_[j]=t;
  243. 					}
  244. 				}
  245.  
  246. 				fill(us, false);
  247. 				target=0;
  248.  
  249. 				int sumScore;
  250. 				if(width>height){
  251. 					sumScore=step1x();
  252. 				}else{
  253. 					sumScore=step1y();
  254. 				}
  255. 				int from=target;
  256.  
  257. 				for(int i=from; i<n; i++){
  258. 					us[_[i]]=false;
  259. 				}
  260.  
  261. 				for(int i=from; i<n; i++){
  262. 					target=i;
  263. 					sumScore+=step2();
  264. 					long end=System.currentTimeMillis();
  265. 					if(end-start>timeLimit){
  266. 						return;
  267. 					}
  268. 				}
  269.  
  270. 				if(sumScore>bestSumScore){
  271. 					bestSumScore=sumScore;
  272. 					updateBest();
  273. 				}
  274. 			}
  275. 		}
  276. 	}
  277.  
  278. 	void updateBest(){
  279. 		System.arraycopy(xs, 0, bestXs, 0, n);
  280. 		System.arraycopy(ys, 0, bestYs, 0, n);
  281. 		System.arraycopy(ws, 0, bestWs, 0, n);
  282. 		System.arraycopy(hs, 0, bestHs, 0, n);
  283. 		System.arraycopy(us, 0, bestUs, 0, n);
  284. 	}
  285.  
  286. 	Answer output(){
  287. 		int[] x1=new int[n];
  288. 		int[] y1=new int[n];
  289. 		int[] x2=new int[n];
  290. 		int[] y2=new int[n];
  291.  
  292. 		// answer.*[i]=*[i]*10
  293. 		for(int i=0; i<n; i++){
  294. 			if(bestUs[i]){
  295. 				x1[i]=bestXs[i];
  296. 				y1[i]=bestYs[i];
  297. 				x2[i]=bestXs[i]+bestWs[i];
  298. 				y2[i]=bestYs[i]+bestHs[i];
  299. 			}else{
  300. 				x1[i]=y1[i]=x2[i]=y2[i]=-10;
  301. 			}
  302. 		}
  303. 		return new Answer(x1, y1, x2, y2);
  304. 	}
  305.  
  306. 	int step1x(){
  307. 		int sumScore=0;
  308. 		int x=marginX;
  309. 		int h=height-2*marginY;
  310. 		for(int i=0; i<n; i++){
  311. 			target=i;
  312. 			int s;
  313. 			if(i%2==0){
  314. 				s=10*h/hs0[_[i]];
  315. 			}else{
  316. 				s=10*h/ws0[_[i]];
  317. 			}
  318. 			s=min(s, 20);
  319. 			s=max(s, 1);
  320. 			if(i%2==0){
  321. 				ws[_[i]]=ws0[_[i]]*s/10;
  322. 				hs[_[i]]=hs0[_[i]]*s/10;
  323. 			}else{
  324. 				ws[_[i]]=hs0[_[i]]*s/10;
  325. 				hs[_[i]]=ws0[_[i]]*s/10;
  326. 			}
  327. 			xs[_[i]]=x;
  328. 			ys[_[i]]=marginY;
  329. 			ts[_[i]]=i%2;
  330. 			ss[_[i]]=s;
  331. 			us[_[i]]=true;
  332. 			if(ys[_[i]]+hs[_[i]]>height){
  333. 				ys[_[i]]=0;
  334. 				if(ys[_[i]]+hs[_[i]]>height){
  335. 					us[_[i]]=false;
  336. 				}
  337. 			}
  338. 			if(xs[_[i]]+ws[_[i]]>width-marginX){
  339. 				us[_[i]]=false;
  340. 				break;
  341. 			}
  342. 			x+=ws[_[i]];
  343. 			if(us[_[i]]){
  344. 				sumScore+=calcScore();
  345. 			}
  346. 		}
  347. 		return sumScore;
  348. 	}
  349.  
  350. 	int step1y(){
  351. 		int sumScore=0;
  352. 		int y=marginY;
  353. 		int w=width-2*marginX;
  354. 		for(int i=0; i<n; i++){
  355. 			target=i;
  356. 			int s;
  357. 			if(i%2==0){
  358. 				s=10*w/hs0[_[i]];
  359. 			}else{
  360. 				s=10*w/ws0[_[i]];
  361. 			}
  362. 			s=min(s, 20);
  363. 			s=max(s, 1);
  364. 			if(i%2==0){
  365. 				ws[_[i]]=hs0[_[i]]*s/10;
  366. 				hs[_[i]]=ws0[_[i]]*s/10;
  367. 			}else{
  368. 				ws[_[i]]=ws0[_[i]]*s/10;
  369. 				hs[_[i]]=hs0[_[i]]*s/10;
  370. 			}
  371. 			xs[_[i]]=marginX;
  372. 			ys[_[i]]=y;
  373. 			ts[_[i]]=(i+1)%2;
  374. 			ss[_[i]]=s;
  375. 			us[_[i]]=true;
  376. 			if(xs[_[i]]+ws[_[i]]>width){
  377. 				xs[_[i]]=0;
  378. 				if(xs[_[i]]+ws[_[i]]>width){
  379. 					us[_[i]]=false;
  380. 				}
  381. 			}
  382. 			if(ys[_[i]]+hs[_[i]]+marginY>height){
  383. 				us[_[i]]=false;
  384. 				break;
  385. 			}
  386. 			y+=hs[_[i]];
  387. 			if(us[_[i]]){
  388. 				sumScore+=calcScore();
  389. 			}
  390. 		}
  391. 		return sumScore;
  392. 	}
  393.  
  394. 	int step2(){
  395. 		final int e4=10000, e8=100000000;
  396.  
  397. 		HashSet<Integer> set=new HashSet<Integer>();
  398. 		set.add(0);
  399. 		set.add(width);
  400. 		set.add(height*e4);
  401. 		set.add(width+height*e4);
  402. 		for(int i=0; i<target; i++){
  403. 			if(!us[_[i]]){
  404. 				continue;
  405. 			}
  406. 			int x=xs[_[i]];
  407. 			int y=ys[_[i]];
  408. 			int w=ws[_[i]];
  409. 			int h=hs[_[i]];
  410. 			for(int k=0; k<dx1.length; k++){
  411. 				set.add((x+dx1[k])+(y+dy1[k])*e4);
  412. 				set.add((x+w+dx1[k])+(y+dy1[k])*e4);
  413. 				set.add((x+dx1[k])+(y+h+dy1[k])*e4);
  414. 				set.add((x+w+dx1[k])+(y+h+dy1[k])*e4);
  415. 			}
  416. 		}
  417.  
  418. 		int index=_[target];
  419. 		us[index]=false;
  420.  
  421. 		ws[index]=min(ws0[index], hs0[index])/10;
  422. 		hs[index]=min(ws0[index], hs0[index])/10;
  423.  
  424. 		ArrayList<Integer> candidate=new ArrayList<Integer>();
  425. 		for(int p : set){
  426. 			int x=p%e4;
  427. 			int y=p/e4;
  428. 			int bit=0;
  429. 			for(int i=0; i<dx2.length; i++){
  430. 				xs[index]=x+dx2[i]*ws[index];
  431. 				ys[index]=y+dy2[i]*hs[index];
  432. 				if(check()){
  433. 					bit|=1<<i;
  434. 				}
  435. 			}
  436. 			if(bit!=0){
  437. 				candidate.add(p+bit*e8);
  438. 			}
  439. 		}
  440.  
  441. 		boolean ok=false;
  442. 		int bestScore=-INF;
  443. 		int bestX=-1, bestY=-1, bestW=-1, bestH=-1, bestT=-1, bestS=-1;
  444.  
  445. 		for(int p : candidate){
  446. 			int x=p%e4;
  447. 			int y=p/e4%e4;
  448. 			int bit=p/e8;
  449. 			for(int k=0; k<2; k++){
  450. 				for(int j=0; j<dx2.length; j++){
  451. 					if((bit>>j&1)==0){
  452. 						continue;
  453. 					}
  454. 					for(int i=0; i<nScales; i++){
  455. 						if(k==0){
  456. 							ws[index]=ws0[index]*scales[i]/10;
  457. 							hs[index]=hs0[index]*scales[i]/10;
  458. 						}else{
  459. 							ws[index]=hs0[index]*scales[i]/10;
  460. 							hs[index]=ws0[index]*scales[i]/10;
  461. 						}
  462. 						if(ws[index]*hs[index]>maxArea){
  463. 							if(scalesOrder==ascending){
  464. 								break;
  465. 							}else{
  466. 								continue;
  467. 							}
  468. 						}
  469.  
  470. 						xs[index]=x+dx2[j]*ws[index];
  471. 						ys[index]=y+dy2[j]*hs[index];
  472. 						ts[index]=k;
  473. 						ss[index]=scales[i];
  474.  
  475. 						if(check()){
  476. 							int score=calcScore();
  477. 							ok=true;
  478. 							if(score>bestScore){
  479. 								bestScore=score;
  480. 								bestX=xs[index];
  481. 								bestY=ys[index];
  482. 								bestW=ws[index];
  483. 								bestH=hs[index];
  484. 								bestT=ts[index];
  485. 								bestS=ss[index];
  486. 							}
  487. 						}else if(scalesOrder==ascending){
  488. 							break;
  489. 						}
  490. 					}
  491. 				}
  492. 			}
  493. 		}
  494.  
  495. 		us[index]=false;
  496. 		if(ok&&(target==0||bestScore>0)){
  497. 			xs[index]=bestX;
  498. 			ys[index]=bestY;
  499. 			ws[index]=bestW;
  500. 			hs[index]=bestH;
  501. 			ts[index]=bestT;
  502. 			ss[index]=bestS;
  503. 			us[index]=true;
  504. 		}
  505.  
  506. 		return us[index]?bestScore:0;
  507. 	}
  508.  
  509. 	boolean check(){
  510. 		// determine whether target's position is valid or not
  511. 		int x=xs[_[target]];
  512. 		int y=ys[_[target]];
  513. 		int w=ws[_[target]];
  514. 		int h=hs[_[target]];
  515. 		if(x<0||x+w>width||y<0||y+h>height){
  516. 			return false;
  517. 		}
  518. 		for(int i=0; i<target; i++){
  519. 			if(us[_[i]]&&overlapStrict(xs[_[i]], ws[_[i]], x, w)
  520. 					&&overlapStrict(ys[_[i]], hs[_[i]], y, h)){
  521. 				return false;
  522. 			}
  523. 		}
  524. 		return true;
  525. 	}
  526.  
  527. 	int calcScore(){
  528. 		// assume no rects overlap
  529. 		int score=0;
  530. 		int x=xs[_[target]];
  531. 		int y=ys[_[target]];
  532. 		int w=ws[_[target]];
  533. 		int h=hs[_[target]];
  534. 		int t=ts[_[target]];
  535. 		for(int i=0; i<target; i++){
  536. 			if(!us[_[i]]){
  537. 				continue;
  538. 			}
  539. 			int x1=max(xs[_[i]], x);
  540. 			int x2=min(xs[_[i]]+ws[_[i]], x+w);
  541.  
  542. 			int y1=max(ys[_[i]], y);
  543. 			int y2=min(ys[_[i]]+hs[_[i]], y+h);
  544.  
  545. 			if(x1<x2&&y1==y2){
  546. 				score+=(ts[_[i]]==t?-1:1)*(x2-x1);
  547. 			}
  548. 			if(y1<y2&&x1==x2){
  549. 				score+=(ts[_[i]]==t?-1:1)*(y2-y1);
  550. 			}
  551. 		}
  552. 		return score;
  553. 	}
  554.  
  555. 	int calcScoreAll(){
  556. 		// assume no rects overlap
  557. 		int score=0;
  558. 		for(int i=0; i<n; i++){
  559. 			if(!us[i]){
  560. 				continue;
  561. 			}
  562. 			for(int j=i+1; j<n; j++){
  563. 				if(!us[j]){
  564. 					continue;
  565. 				}
  566. 				int x1=max(xs[i], xs[j]);
  567. 				int x2=min(xs[i]+ws[i], xs[j]+ws[j]);
  568.  
  569. 				int y1=max(ys[i], ys[j]);
  570. 				int y2=min(ys[i]+hs[i], ys[j]+hs[j]);
  571.  
  572. 				if(x1<x2&&y1==y2){
  573. 					score+=(ts[i]==ts[j]?-1:1)*(x2-x1);
  574. 				}
  575. 				if(y1<y2&&x1==x2){
  576. 					score+=(ts[i]==ts[j]?-1:1)*(y2-y1);
  577. 				}
  578. 			}
  579. 		}
  580. 		return score;
  581. 	}
  582.  
  583. 	boolean overlap(int x1, int w1, int x2, int w2){
  584. 		return x1<=x2+w2&&x2<=x1+w1;
  585. 	}
  586.  
  587. 	boolean overlapStrict(int x1, int w1, int x2, int w2){
  588. 		return x1<x2+w2&&x2<x1+w1;
  589. 	}
  590.  
  591. 	void shuffleSmall(int[] is){
  592. 		for(int i=is.length-1; i>=1; i--){
  593. 			int j=xorShift.nextInt(i+1);
  594. 			int t=is[i];
  595. 			is[i]=is[j];
  596. 			is[j]=t;
  597. 		}
  598. 	}
  599.  
  600. 	void shuffleLarge(int[] is, int from){
  601. 		for(int i=is.length-1; i>=from+1; i--){
  602. 			int j=xorShift.nextInt(i-from+1)+from;
  603. 			int t=is[i];
  604. 			is[i]=is[j];
  605. 			is[j]=t;
  606. 		}
  607. 	}
  608.  
  609. 	void lock(){
  610. 		if(debug){
  611. 			for(; lock;){
  612. 				try{
  613. 					Thread.sleep(2);
  614. 				}catch(InterruptedException e){
  615. 					e.printStackTrace();
  616. 				}
  617. 			}
  618. 			lock=true;
  619. 		}
  620. 	}
  621.  
  622. 	void println(String s){
  623. 		System.out.println(s);
  624. 	}
  625.  
  626. 	void print(String s){
  627. 		System.out.print(s);
  628. 	}
  629.  
  630. 	void debug(Object... os){
  631. 		System.err.println(Arrays.deepToString(os));
  632. 	}
  633.  
  634. 	public static void main(String[] args){
  635. 		new A().run();
  636. 	}
  637.  
  638. }
  639.  
  640. class Xorshift{
  641.  
  642. 	int x, y, z, w;
  643.  
  644. 	public Xorshift(){
  645. 		x=123456789;
  646. 		y=362436069;
  647. 		z=521288629;
  648. 		w=88675123;
  649. 	}
  650.  
  651. 	public Xorshift(int seed){
  652. 		x=_(seed, 0);
  653. 		y=_(x, 1);
  654. 		z=_(y, 2);
  655. 		w=_(z, 3);
  656. 	}
  657.  
  658. 	int _(int s, int i){
  659. 		return 1812433253*(s^(s>>>30))+i+1;
  660. 	}
  661.  
  662. 	// 32bit signed
  663. 	public int nextInt(){
  664. 		int t=x^(x<<11);
  665. 		x=y;
  666. 		y=z;
  667. 		z=w;
  668. 		return w=w^(w>>>19)^t^(t>>>8);
  669. 	}
  670.  
  671. 	// error = O(n*2^-32)
  672. 	public int nextInt(int n){
  673. 		return (int)(n*nextDouble());
  674. 	}
  675.  
  676. 	// [0, 1) (53bit)
  677. 	public double nextDouble(){
  678. 		int a=nextInt()>>>5, b=nextInt()>>>6;
  679. 		return (a*67108864.0+b)*(1.0/(1L<<53));
  680. 	}
  681.  
  682. }
  683.  
  684. class Pair implements Comparable<Pair>{
  685. 	int key;
  686. 	double value;
  687.  
  688. 	Pair(int key, double value){
  689. 		this.key=key;
  690. 		this.value=value;
  691. 	}
  692.  
  693. 	@Override
  694. 	public int compareTo(Pair p){
  695. 		return Double.compare(value, p.value);
  696. 	}
  697. }
  698.  
  699. class Param{
  700. 	int w, h, n;
  701. 	int[] ws, hs;
  702.  
  703. 	Param(int w, int h, int n, int[] ws, int[] hs){
  704. 		this.w=w;
  705. 		this.h=h;
  706. 		this.n=n;
  707. 		this.ws=ws.clone();
  708. 		this.hs=hs.clone();
  709. 	}
  710. }
  711.  
  712. class Answer{
  713. 	int[] x1, y1, x2, y2;
  714. 	int n;
  715.  
  716. 	Answer(int[] x1, int[] y1, int[] x2, int[] y2){
  717. 		this.x1=x1.clone();
  718. 		this.y1=y1.clone();
  719. 		this.x2=x2.clone();
  720. 		this.y2=y2.clone();
  721. 		n=x1.length;
  722. 	}
  723. }
  724.  
  725. class Scanner{
  726. 	BufferedReader br;
  727. 	StringTokenizer st;
  728.  
  729. 	Scanner(InputStream in){
  730. 		br=new BufferedReader(new InputStreamReader(in));
  731. 		eat("");
  732. 	}
  733.  
  734. 	void eat(String s){
  735. 		st=new StringTokenizer(s);
  736. 	}
  737.  
  738. 	String nextLine(){
  739. 		try{
  740. 			return br.readLine();
  741. 		}catch(IOException e){
  742. 			throw new IOError(e);
  743. 		}
  744. 	}
  745.  
  746. 	boolean hasNext(){
  747. 		while(!st.hasMoreTokens()){
  748. 			String s=nextLine();
  749. 			if(s==null)
  750. 				return false;
  751. 			eat(s);
  752. 		}
  753. 		return true;
  754. 	}
  755.  
  756. 	String next(){
  757. 		hasNext();
  758. 		return st.nextToken();
  759. 	}
  760.  
  761. 	int nextInt(){
  762. 		return Integer.parseInt(next());
  763. 	}
  764. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bFhm3
language:
Java (HotSpot 12)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!