{"problem":{"name":"C. Crazy Dreamoon","description":{"content":"Dreamoon likes algorithm competitions very much. But when he feels crazy because he cannot figure out any solution for any problem in a competition, he often draws many meaningless straight line segme","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10123C"},"statements":[{"statement_type":"Markdown","content":"Dreamoon likes algorithm competitions very much. But when he feels crazy because he cannot figure out any solution for any problem in a competition, he often draws many meaningless straight line segments on his calculation paper.\n\nDreamoon's calculation paper is special: it can be imagined as the plane with Cartesian coordinate system with range [0, 2000 × [0, 2000]] for the coordinates. The grid lines are all lines of the form x = c or y = c for every integer c between 0 and 2000, inclusive. So, the grid contains 2000 × 2000 squares.\n\nNow, Dreamoon wonders how many grid squares are crossed by at least one of the lines he drew. Please help Dreamoon find the answer. Note that, to cross a square, a segment must contain an interior point of the square.\n\nThe first line of input contains an integer N denoting the number of lines Dreamoon draw. The i-th line of following N lines contains four integers xi1, yi1, xi2, yi2, denoting that the i-th segment Dreamoon drew is a straight line segment between points (xi1, yi1) and (xi2, yi2).\n\nOutput one integer on a single line: how many grid squares are crossed by at least one of the line segments which Dreamoon drew.\n\n## Input\n\nThe first line of input contains an integer N denoting the number of lines Dreamoon draw. The i-th line of following N lines contains four integers xi1, yi1, xi2, yi2, denoting that the i-th segment Dreamoon drew is a straight line segment between points (xi1, yi1) and (xi2, yi2).  1 ≤ N ≤ 2 × 103  0 ≤ xi1, yi1, xi2, yi2 ≤ 2 × 103  the lengths of all line segments in input are non-zero \n\n## Output\n\nOutput one integer on a single line: how many grid squares are crossed by at least one of the line segments which Dreamoon drew.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of line segments.  \nFor each $ i \\in \\{1, \\dots, N\\} $, let $ L_i $ be a line segment defined by endpoints $ (x_{i1}, y_{i1}) $ and $ (x_{i2}, y_{i2}) $, where $ x_{ij}, y_{ij} \\in [0, 2000] \\cap \\mathbb{Z} $.\n\nLet $ \\mathcal{S} = \\{ [a, a+1] \\times [b, b+1] \\mid a, b \\in \\{0, 1, \\dots, 1999\\} \\} $ be the set of all unit grid squares in the $ 2000 \\times 2000 $ grid.\n\n**Constraints**  \n1. $ 1 \\le N \\le 1000 $  \n2. For each $ i $, $ 0 \\le x_{i1}, y_{i1}, x_{i2}, y_{i2} \\le 2000 $  \n\n**Objective**  \nCompute the cardinality of the set:  \n$$\n\\left| \\left\\{ S \\in \\mathcal{S} \\mid \\exists\\, i \\in \\{1, \\dots, N\\} \\text{ such that } L_i \\cap \\text{int}(S) \\neq \\emptyset \\right\\} \\right|\n$$  \nwhere $ \\text{int}(S) $ denotes the interior of square $ S $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10123C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}