Sub Chocolate & paint area

Split chocolate

package lanqiao;


import java.util.Scanner;

/**
 * Created by ministrong on 2020/3/2.
 *
 *
  title ：  Split chocolate 

  There was... On children's day K Three children come to Xiaoming's house to visit . Xiao Ming took out his collection of chocolates to entertain the children .
  Xiao Ming has N A piece of chocolate , Among them the first i Block is Hi x Wi A rectangle of squares .

  For the sake of fairness , Xiaoming needs to come from here  N  Cut out a piece of chocolate K Give the children a piece of chocolate . The cut chocolate needs to satisfy ：

 1.  The shape is square , The side length is an integer 
 2.  Same size 

  For example, a piece of 6x5 The chocolate can be cut out 6 block 2x2 Of chocolate or 2 block 3x3 Of chocolate .

  Of course, children want to get as much chocolate as possible , You can help me Hi Calculate the maximum side length ？

  Input 
  The first line contains two integers N and K.(1 <= N, K <= 100000)
  following N Each line contains two integers Hi and Wi.(1 <= Hi, Wi <= 100000)
  Input to ensure that each child can get at least one piece of 1x1 Of chocolate .

  Output 
  Output the maximum possible side length of the cut square chocolate .

  The sample input ：
 2 10
 6 5
 5 6

  Sample output ：
 2

  Resource Convention ：
  Peak memory consumption （ Including virtual machines ） < 256M
 CPU Consume   < 1000ms


  Please output strictly as required , Don't print like that ：“ Please input ...”  Extra content of .

  All code in the same source file , After debugging , Copy and submit the source code .
  Do not use package sentence . Do not use jdk1.7 And above .
  The name of the main class must be ：Main, Otherwise, it will be treated as invalid code .

 */


/**
 *  The first idea is to solve by violence , From side length len=100000 Start calculating whether you can separate k Block , Can't just len--
 *  But that's how it works , It's almost a cycle. At worst, it's a cycle 100000*100000 Time , It's bound to time out , So this question should be about the optimization of enumeration 
 *  Use dichotomy to optimize 
 */


public class Q9_2017_8_fenqiaoke {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int k=in.nextInt();
        int[] Hi=new int[n];
        int[] Wi=new int[n];
        for(int i=0;i<n;i++){
            Hi[i]=in.nextInt();
            Wi[i]=in.nextInt();
        }

        int l=1;
        int r=100001;
        int res=1;
        while(l<=r){
            int mid=(l+r)/2;
            int t=0;
            for(int i=0;i<n;i++){
                t+=(Hi[i]/mid)*(Wi[i]/mid);
            }
            if(t>=k){
                l=mid+1;
                res=mid;
            }
            else{
                r=mid-1;
            }
        }

        System.out.println(res);


    }
}

Paint area

package lanqiao;

import java.util.HashMap;
import java.util.Scanner;

/**
 * Created by ministrong on 2020/3/2.
 *
  title ： Paint area 

 X A group of archaeological robots on the planet are doing archaeology on a piece of ruins .
  The ground in this area is as hard as stone 、 Flat as a mirror .
  Management staff for convenience , Established a standard rectangular coordinate system .

  Every robot has its own specialty 、 great talent . They're also interested in different things .
  After all kinds of measurements , Each robot reports one or more rectangular areas , As a priority archaeological area .

  The format of rectangle is (x1,y1,x2,y2), Represents the coordinates of the two diagonal points of the rectangle .

  In order to stand out , The headquarters requires that all the selected rectangular areas of robots be painted yellow .
  Xiao Ming doesn't need to be a painter , It's just that he needs to calculate , How much paint does it take .

  In fact, it is not difficult , Just figure out how much area all the rectangles cover .
  Be careful , The rectangles may overlap .

  The input of this problem is several rectangles , The total area covered by the output is required .

  Input format ：
  first line , An integer n, How many rectangles are there (1<=n<10000)
  Next n That's ok , Each row has 4 It's an integer x1 y1 x2 y2, Space apart , Represents the coordinates of two diagonal vertices of a rectangle .
 (0<= x1,y1,x2,y2 <=10000)

  Output format ：
  One line, one integer , Represents the total area covered by the rectangle .

  for example ,
  Input ：
 3
 1 5 10 10
 3 1 20 20
 2 7 15 17

  The program should output ：
 340

  Another example is ,
  Input ：
 3
 5 2 10 6
 2 7 12 10
 8 1 15 15

  The program should output ：
 128

  Resource Convention ：
  Peak memory consumption （ Including virtual machines ） < 256M
 CPU Consume   < 2000ms


  Please output strictly as required , Don't print like that ：“ Please input ...”  Extra content of .

  All code in the same source file , After debugging , Copy and submit the source code .
  Do not use package sentence . Do not use jdk1.7 And above .
  The name of the main class must be ：Main, Otherwise, it will be treated as invalid code .


 */

/**
 *  The first choice for making the Blue Bridge Cup is to get points first , That is, when you can't think of a solution for the time being , The use of violence can be directly considered , Let's see if we can optimize 
 *  For each input matrix , Set a matrix of flags flag, Then the cycle 
 */
public class Q10_2017_8_youqi {

    public static void main(String[] args) {

        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int[][] a=new int[n][2];
        int[][] b=new int[n][2];
        boolean[][] flag=new boolean[10001][10001];
        // The abscissa of the lower left corner is the same as a The subscript 
        HashMap<Integer,Integer> map=new HashMap<>();
        int res=0;
        int[] ax=new int[n];
        for(int i=0;i<n;i++){
            a[i][0]=in.nextInt();
            a[i][1]=in.nextInt();
            b[i][0]=in.nextInt();
            b[i][1]=in.nextInt();
            for(int j=a[i][0];j<b[i][0];j++){
                for(int z=a[i][1];z<b[i][1];z++){
                    if(!flag[j][z]){
                        res++;
                        flag[j][z]=true;
                    }
                }
            }
        }
        System.out.println(res);

    }
}