{"raw_statement":[{"iden":"statement","content":"Hence, she will proceed as follows. She chooses two monuments, that we will call the #cf_span(class=[tex-font-style-underline], body=[boundary monuments]), and asks the balloon pilot to go between these monuments. From there, she takes two $180^compose$ pictures: each picture shows one side of Paris, both sides being delimited by the two boundary monuments. Each picture receives a grade, which is the sum of the grades of the monuments that it shows, including the boundary monuments on both pictures. Finally, if the pictures have grades A and B, the goal of Morgane is to minimize the difference between A and B (in absolute value).\n\nThe visibility from the balloon is such that all monuments can be seen in either of the two photographs.\n\nYou must assist Morgane in choosing appropriate boundary monuments. In order to do this, you are given a list of the monuments. For every monument visited by Morgane, this list contains a line which indicates the Cartesian coordinates of the monument location, along with the monument's grade. You should give the minimal possible difference, among all pairs of pictures that Morgane may take, between the grades of the two pictures.\n\n*Important Note*\n\nMorgane was so precise at locating every monument that no three monuments are on a same straight line.\n\nThe input comprises several lines, each consisting of integers separated with single spaces: \n\n*Limits*\n\nThe output should consist of a single line, whose content is an integer, the minimal difference (in absolute value) between the grades of a pair of photographs that Morgane may take.\n\n"},{"iden":"input","content":"The input comprises several lines, each consisting of integers separated with single spaces:   the first line contains the number N of monuments;  each of the N next lines contains three integers associated with each monument: the X coordinate, the Y coordinate and the grade G of the monument represented on that line. *Limits*  $2 <= N <= 4000$;  $0 <= X, \" \"Y <= 1000000000$ and $1 <= G <= 1000000000$. "},{"iden":"output","content":"The output should consist of a single line, whose content is an integer, the minimal difference (in absolute value) between the grades of a pair of photographs that Morgane may take."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of monuments.  \nFor each monument $ i \\in \\{1, \\dots, n\\} $, let $ (x_i, y_i) \\in \\mathbb{R}^2 $ be its Cartesian coordinates and $ g_i \\in \\mathbb{Z} $ be its grade.  \n\nLet $ \\mathcal{P} = \\{ (i, j) \\mid 1 \\leq i < j \\leq n \\} $ be the set of all unordered pairs of distinct monuments, representing potential boundary monument pairs.  \n\nFor each pair $ (i, j) \\in \\mathcal{P} $, the line through monuments $ i $ and $ j $ divides the plane into two half-planes. Let $ S_{ij}^+ $ and $ S_{ij}^- $ be the sets of monument indices lying strictly in each open half-plane (excluding $ i $ and $ j $).  \n\nDefine the grade of each photograph as:  \n- $ A_{ij} = g_i + g_j + \\sum_{k \\in S_{ij}^+} g_k $  \n- $ B_{ij} = g_i + g_j + \\sum_{k \\in S_{ij}^-} g_k $  \n\n**Constraints**  \n1. No three monuments are collinear.  \n2. All monument coordinates and grades are given as integers.  \n\n**Objective**  \nCompute:  \n$$\n\\min_{(i,j) \\in \\mathcal{P}} \\left| A_{ij} - B_{ij} \\right|\n$$","simple_statement":"Given a set of monuments with positions and grades, choose two boundary monuments to split all monuments into two groups (left and right of the line between them). Each group’s grade is the sum of grades of monuments on that side. Find the minimum possible absolute difference between the two group grades.","has_page_source":false}