geometry | brain

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.11 Rectangle Union Area

17.11 Rectangle Union Area Problem Given a set of axis-aligned rectangles, compute the total area covered by their union. The rectangles may overlap. Overlapping regions should be counted once, not once per rectangle. For example: +---------+ | | | +---------+ | | | | +-----|---+ | | | +---------+ The total area is not: area(rectangle 1) + area(rectangle 2) because the shared region would be counted twice. This problem appears...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.12 Half-Plane Intersection

17.12 Half-Plane Intersection Problem Given a collection of half-planes, compute their common intersection. A half-plane is one side of a line. For example: x ≥ 0 y ≥ 0 x + y ≤ 5 each describes an infinite region of the plane. The goal is to find the region satisfying all constraints simultaneously. Applications include: Linear programming in two dimensions Visibility problems Motion planning Convex clipping Computational optimization Voronoi diagram...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.2 Orientation Tests

17.2 Orientation Tests Problem Many geometric algorithms must determine whether three points form a left turn, a right turn, or lie on the same line. This seemingly simple question appears in convex hull construction, segment intersection detection, polygon processing, triangulation, and sweep-line algorithms. An efficient and reliable solution is required because orientation tests often execute millions of times in large geometric workloads. Solution Use the sign of a cross product....

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.22 Correctness Proofs

17.22 Correctness Proofs Problem Geometric algorithms are easy to test visually and surprisingly easy to get wrong. A convex hull may look correct on ordinary inputs but fail on collinear points. A sweep-line algorithm may work for separated rectangles but miscount shared boundaries. A point-in-polygon test may pass random examples but fail when the query point lies exactly on an edge. To trust a geometric algorithm, you need more than...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.23 Testing Geometry Algorithms

17.23 Testing Geometry Algorithms Problem Geometry code fails in ways that ordinary examples rarely expose. A convex hull may work for a random cloud of points but fail when all points are collinear. A segment intersection routine may pass crossing cases but fail on shared endpoints. A point-in-polygon test may classify ordinary points correctly but break when the query point lies exactly on a vertex. Testing geometry algorithms requires deliberate...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.3 Line and Segment Intersection

17.3 Line and Segment Intersection Problem Given two lines or two line segments, determine whether they intersect and, if they do, compute the intersection point. This problem appears throughout computational geometry. Computer graphics uses intersection tests during rendering. Geographic information systems use them when processing roads, rivers, and administrative boundaries. Robotics uses them for collision detection and motion planning. Polygon clipping, sweep-line algorithms, and triangulation all rely heavily on robust...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.14 Delaunay Triangulation Overview

17.14 Delaunay Triangulation Overview Problem Given a set of points in the plane, construct a triangulation that avoids thin, poorly shaped triangles as much as possible. A triangulation connects points with noncrossing edges so that the convex hull is divided into triangles. Many triangulations are possible for the same point set. Some produce skinny triangles, which are undesirable in interpolation, finite element methods, rendering, terrain modeling, and mesh generation. The...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.25 Case Studies

17.25 Case Studies Problem Individual geometry algorithms are useful, but real systems usually require several of them working together. A practical geometry task rarely says only: compute a convex hull or: test one segment intersection Instead, it asks for a result such as: find all buildings inside a map region detect collisions among moving objects measure total occupied area simplify a point cloud plan a path through obstacles These tasks...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.9 Sweep Line Algorithms

17.9 Sweep Line Algorithms Problem Many geometric problems involve detecting interactions among large collections of geometric objects. Examples include: Finding all segment intersections Computing rectangle union area Detecting overlapping intervals Processing geographic boundaries Building visibility graphs Event scheduling and timeline analysis A straightforward approach often compares every object with every other object. For example, checking whether any two of n line segments intersect requires: O(n²) pairwise comparisons. This becomes prohibitively...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.5 Point in Polygon

17.5 Point in Polygon Problem Given a polygon and a query point, determine whether the point lies: inside the polygon outside the polygon on the boundary This problem appears in geographic information systems, computer graphics, collision detection, CAD software, robotics, game engines, and spatial databases. A map application may need to determine which administrative region contains a GPS coordinate. A game engine may need to determine whether a character is...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.10 Interval Geometry

17.10 Interval Geometry Problem You need to solve geometric problems that can be reduced to one-dimensional intervals. Many two-dimensional problems contain an interval subproblem. Rectangle union, line sweep algorithms, calendar conflicts, range coverage, collision detection, and spatial indexing all require operations such as: insert an interval delete an interval merge overlapping intervals measure total covered length find whether a point is covered find maximum overlap Getting interval geometry right is...

Programming › Algorithm Cookbook ›

Chapter 17. Computational Geometry

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.8 Closest Pair of Points

17.8 Closest Pair of Points Problem Given a set of points in the plane, find the pair with the smallest Euclidean distance. A brute-force solution compares every pair of points. For n points, that requires: O(n²) distance checks. That is acceptable for small input, but it becomes impractical for large point sets. The closest-pair problem needs a faster method. Solution Use divide and conquer. The high-level structure is: sort points...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.18 Geometric Hashing

17.18 Geometric Hashing Problem You need a fast way to group or search geometric objects by location. Examples include: nearby point lookup collision broad-phase detection duplicate point detection spatial clustering map tile indexing particle simulation nearest-neighbor candidates A brute-force search compares every object with every other object. For n objects, that costs: O(n²) Geometric hashing reduces this cost by placing objects into spatial buckets. Instead of searching the whole dataset,...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.24 Performance Optimization

17.24 Performance Optimization Problem Many geometric algorithms are already asymptotically optimal. For example: convex hull O(n log n) closest pair O(n log n) rectangle union O(n log n) KD-tree query O(log n) average Yet practical implementations can still be slow. The reason is that geometric software often spends most of its time in: predicate evaluation memory allocation sorting cache misses candidate generation repeated computations Performance optimization in geometry is therefore...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.21 Geometry Design Patterns

17.21 Geometry Design Patterns Problem After studying individual geometric algorithms, it is tempting to view them as unrelated techniques. You may have encountered: convex hulls sweep lines Voronoi diagrams Delaunay triangulations spatial indexes segment trees rotating calipers polygon clipping At first glance, these algorithms appear completely different. In practice, however, most computational geometry systems are built from a surprisingly small collection of recurring design patterns. Understanding these patterns is often...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.7 Rotating Calipers

17.7 Rotating Calipers Problem After constructing a convex hull, many geometric questions remain: What is the maximum distance between any two points? What is the width of the shape? Which pair of parallel supporting lines are farthest apart? What is the minimum bounding rectangle? A naive approach often examines every pair of hull vertices. For a hull containing h vertices: O(h²) comparisons may be required. For large geometric datasets, this...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.1 Points and Vectors

17.1 Points and Vectors Problem You need a mathematical representation for locations, directions, distances, and geometric relationships. Nearly every computational geometry algorithm depends on a small set of operations involving points and vectors. Before implementing line intersections, convex hulls, closest-pair searches, or polygon algorithms, you must understand how points and vectors are represented and manipulated. Solution Represent a point as a coordinate in space and represent a vector as a...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.17 Floating-Point Robustness

17.17 Floating-Point Robustness Problem Some geometric problems cannot stay entirely in integer arithmetic. Examples include: line intersections circle intersections rotations projections normalization physics simulation computer graphics geographic coordinates These computations naturally produce real-valued coordinates. Floating-point arithmetic is fast and widely supported, but it introduces rounding, cancellation, overflow, underflow, and comparison errors. The goal is not to avoid floating point entirely. The goal is to use it deliberately enough that algorithms...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.6 Convex Hull

17.6 Convex Hull Problem Given a set of points, compute the smallest convex polygon that contains all of them. This polygon is called the convex hull. You can think of it as the shape formed by stretching a rubber band around the outside of the point set and letting it snap tight. Convex hulls appear in collision detection, pattern recognition, geographic analysis, robotics, image processing, computational geometry, and optimization. They...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.4 Polygon Area

17.4 Polygon Area Problem Given a polygon described by its vertices, compute its area efficiently and accurately. Polygon area computation appears in computer graphics, geographic information systems, computer-aided design, simulation systems, image processing, and computational geometry. Many higher-level algorithms depend on area calculations, including centroid computation, polygon clipping, mesh processing, convex hull analysis, and geometric optimization. A solution should work for convex and non-convex polygons while remaining efficient for large...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.13 Voronoi Diagrams Overview

17.13 Voronoi Diagrams Overview Problem Given a set of points, partition the plane into regions so that every location belongs to the region of its nearest point. The input points are usually called sites. A Voronoi diagram answers questions like: Which hospital is closest to this address? Which cell tower should serve this device? Which warehouse is nearest to this customer? Which sample point owns this part of the plane?...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.16 Integer Geometry

17.16 Integer Geometry Problem Many computational geometry problems use coordinates that are naturally integers: grid maps pixels game worlds GIS tiles CAD layouts competitive programming datasets In these settings, floating-point arithmetic often introduces unnecessary complexity. A segment intersection test that should be exact may fail because of rounding. A convex hull algorithm may classify collinear points incorrectly. A polygon area computation may lose precision even though every input coordinate is...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.19 Spatial Indexes

17.19 Spatial Indexes Problem You need to search large collections of geometric objects efficiently. Common queries include: find all points inside this rectangle find objects near this location find candidate collisions find the nearest object find all shapes intersecting this window A brute-force scan checks every object. For n objects, each query costs: O(n) That may be fine for small datasets, but it fails for maps, games, CAD files, simulations,...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.15 Precision Errors

17.15 Precision Errors Problem Geometric algorithms often look exact on paper but fail in code because numeric computations are approximate. A segment intersection test may say two segments do not intersect when they barely touch. A convex hull algorithm may remove the wrong point because a nearly collinear turn is misclassified. A polygon area calculation may lose meaningful digits when coordinates are large and differences are small. The difficulty is...

Programming › Algorithm Cookbook › Chapter 17. Computational Geometry ›

17.20 Geometry Libraries and Practical Patterns

17.20 Geometry Libraries and Practical Patterns Problem Most real-world geometry software is not built from a single algorithm. A mapping system may use: point-in-polygon spatial indexes polygon clipping bounding boxes coordinate transforms A CAD application may use: line intersections half-plane constraints mesh generation topological validation A game engine may use: collision detection broad-phase indexing ray casting convex hulls The challenge is not merely implementing individual algorithms. The challenge is combining...

Practice › Codeforces Solutions › Educational Codeforces Round 189 (Rated for Div. 2) ›

CF 2225E - Covering Points with Circles

CF 2225E - Covering Points with Circles Rating: - Tags: constructive algorithms, geometry, math Solve time: 2m 37s Verified: no Solution Problem Understanding We are given up to $10^4$ integer points on the plane and a fixed radius $r$. We must output the centers of several circles, all having radius $r$, such that the centers have integer coordinates and no two circles overlap in positive area. Touching is allowed, but...

Practice › Codeforces Solutions › April Fools Day Contest 2024 ›

CF 1952I - Dark Matter

CF 1952I - Dark Matter Rating: - Tags: *special, bitmasks, geometry Solve time: 48s Verified: yes Solution Problem Understanding The input describes a single arithmetic-style expression consisting of integers combined with the + operator. The key difference from standard arithmetic is that + does not mean numeric addition. Instead, each operation combines two numbers by treating them as binary strings and stitching them together. Concretely, when we see an expression...

Practice › Codeforces Solutions › CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1942C1 - Bessie's Birthday Cake (Easy Version)

CF 1942C1 - Bessie's Birthday Cake (Easy Version) Rating: 1300 Tags: geometry, greedy, math Solve time: 56s Verified: yes Solution Problem Understanding We are given a regular polygon with $n$ vertices representing a cake. Some vertices are already selected by Bessie as potential endpoints for drawing diagonals. Each diagonal connects two chosen vertices, and the goal is to maximize the number of triangles formed by non-intersecting diagonals among these selected...

Practice › Codeforces Solutions ›

CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)

CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) Type: Div. 1+2 | Problems: 9 | Verified: 4/9 | Rating range: 800-3500 | Time: 16m 46s Problem Name Rating Tags Solve Time Verified A Farmer John's Challenge 800 constructive-algorithms, math 1m 37s ✗ B Bessie and MEX 1100 constructive-algorithms, math 1m 18s ✗ C1 Bessie's Birthday Cake (Easy Version) 1300 geometry, greedy, math 56s ✓ C2 Bessie's Birthday Cake...

Practice › Codeforces Solutions › European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) ›

CF 1949A - Grove

CF 1949A - Grove Rating: 3300 Tags: brute force, dfs and similar, dp, geometry, probabilities Solve time: 2m 41s Verified: yes Solution Problem Understanding Every tree is planted at an integer lattice point. Around that point we place a disk of radius r , representing the root system. Two conditions must hold. The entire disk must stay inside the square lawn. Since the lawn is the square [0,n] × [0,n]...

Practice › Codeforces Solutions ›

European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)

European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) Type: ICPC/IOI | Problems: 11 | Verified: 5/11 | Rating range: 1500-3300 | Time: 28m 1s Problem Name Rating Tags Solve Time Verified A Grove 3300 brute-force, dfs-and-similar, dp 2m 41s ✓ B Charming Meals 1500 binary-search, brute-force, greedy 1m 44s ✓ C Annual Ants' Gathering 1900 dfs-and-similar, dp, greedy 4m 48s ✓ D Funny or Scary? 2600 constructive-algorithms...

Practice › Codeforces Solutions › CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1942C2 - Bessie's Birthday Cake (Hard Version)

CF 1942C2 - Bessie's Birthday Cake (Hard Version) Rating: 1700 Tags: geometry, greedy, math Solve time: 2m 8s Verified: no Solution Problem Understanding We have a regular polygon with n vertices arranged on a circle. Some x vertices are already available for use. We may additionally choose at most y more vertices. After selecting vertices, we are allowed to draw non-intersecting diagonals whose endpoints belong to the selected set. Every...

Practice › LeetCode › LeetCode 34xx ›

LeetCode 3464 - Maximize the Distance Between Points on a Square

LeetCode Problem 3464 Difficulty: 🔴 Hard Topics: Array, Math, Binary Search, Geometry, Sorting Solution LeetCode 3464 - Maximize the Distance Between Points on a Square Problem Understanding We are given a square of side length side . Every point in the input lies somewhere on the boundary of this square. We must choose exactly k points from the given set. For any two selected points, we can compute their Manhattan...

Practice › LeetCode › LeetCode 36xx ›

LeetCode 3625 - Count Number of Trapezoids II

LeetCode Problem 3625 Difficulty: 🔴 Hard Topics: Array, Hash Table, Math, Geometry Solution Problem Understanding The problem asks us to count the number of unique trapezoids that can be formed from a set of points on a 2D Cartesian plane. Each point is given as a pair of integers representing its x and y coordinates. A trapezoid is defined as a convex quadrilateral with at least one pair of parallel...

Practice › LeetCode › LeetCode 35xx ›

LeetCode 3588 - Find Maximum Area of a Triangle

LeetCode Problem 3588 Difficulty: 🟡 Medium Topics: Array, Hash Table, Math, Greedy, Geometry, Enumeration Solution LeetCode 3588 - Find Maximum Area of a Triangle Problem Understanding We are given n distinct points on a 2D Cartesian plane. Each point is represented as [x, y] . We must choose any three points that form a non-degenerate triangle, meaning the area must be strictly greater than zero. Among all valid triangles, we...

Practice › Codeforces Solutions › Codeforces Round 262 (Div. 2) ›

CF 460E - Roland and Rose

CF 460E - Roland and Rose Rating: 2700 Tags: brute force, geometry, math, sortings Solve time: 1m 15s Verified: yes Solution Problem Understanding Roland wants to place n watch towers on a 2D integer grid around a rose at the origin so that the sum of squared distances between all pairs of towers is maximized. Each tower must lie within or on a circle of radius r centered at (0,0)....

Practice › Codeforces Solutions › Codeforces Round 265 (Div. 1) ›

CF 464B - Restore Cube

CF 464B - Restore Cube Rating: 2000 Tags: brute force, geometry Solve time: 5m 14s Verified: no Solution

Practice › Codeforces Solutions ›

Codeforces Round 265 (Div. 1)

Codeforces Round 265 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 0/3 | Rating range: 2000-3000 | Time: 15m 43s Problem Name Rating Tags Solve Time Verified B Restore Cube 2000 brute-force, geometry 5m 14s ✗ D World of Darkraft - 2 2700 dp, probabilities 5m 15s ✗ E The Classic Problem 3000 data-structures, graphs, shortest-paths 5m 14s ✗

Practice › Codeforces Solutions ›

MemSQL Start[c]UP 2.0 - Round 1

MemSQL Start[c]UP 2.0 - Round 1 Type: Special | Problems: 5 | Verified: 4/5 | Rating range: 1000-2700 | Time: 9m 36s Problem Name Rating Tags Solve Time Verified A Eevee 1000 brute-force, implementation, strings 1m 6s ✓ B 4-point polyline 1800 brute-force, constructive-algorithms, geometry 2m 2s ✓ C Magic Trick 2100 combinatorics, math, probabilities 1m 44s ✓ E Three strings 2400 data-structures, dsu, string-suffix-structures 2m 7s ✓ F Permutation...

Practice › Codeforces Solutions › MemSQL Start[c]UP 2.0 - Round 1 ›

CF 452B - 4-point polyline

CF 452B - 4-point polyline Rating: 1800 Tags: brute force, constructive algorithms, geometry, trees Solve time: 2m 2s Verified: yes Solution Problem Understanding We have all lattice points inside and on the boundary of an axis-aligned rectangle whose opposite corners are (0, 0) and (n, m) . The task is to choose four distinct lattice points and connect them in the chosen order. The resulting polyline contains three segments, from...

Practice › Codeforces Solutions ›

Codeforces Round 271 (Div. 2)

Codeforces Round 271 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 6/6 | Rating range: 900-2100 | Time: 9m 19s Problem Name Rating Tags Solve Time Verified A Keyboard 900 implementation 1m 4s ✓ B Worms 1200 binary-search, implementation 1m 36s ✓ C Captain Marmot 2000 brute-force, geometry 1m 12s ✓ D Flowers 1700 dp 1m 50s ✓ E Pillars 2000 binary-search, data-structures, dp 2m 1s ✓ F...

Practice › Codeforces Solutions › Codeforces Round 271 (Div. 2) ›

CF 474C - Captain Marmot

CF 474C - Captain Marmot Rating: 2000 Tags: brute force, geometry Solve time: 1m 12s Verified: yes Solution Problem Understanding We are asked to help Captain Marmot organize his regiments of moles so that each group of four forms a perfect square on a plane. Each mole starts at a position (xi, yi) and has a “home” at (ai, bi) . The only allowed operation is to rotate a mole...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3025 - Find the Number of Ways to Place People I

LeetCode Problem 3025 Difficulty: 🟡 Medium Topics: Array, Math, Geometry, Sorting, Enumeration Solution Problem Understanding The problem gives us a list of distinct points on a 2D plane. Each point is represented as [x, y] , where x is the horizontal coordinate and y is the vertical coordinate. We must count how many ordered pairs (A, B) satisfy two conditions: Point A is on the upper-left side of point B...

Practice › Mathematics › IMO Shortlist › IMO 2000 Shortlist ›

IMO 2000 SL G4

IMO 2000 SL G4 Origin: RUS | Category: Geometry Problem Let A1A2 . . . An be a convex polygon, n \geq4. Prove that A1A2 . . . An is cyclic if and only if to each vertex Aj one can assign a pair (bj, cj) of real numbers, j = 1, 2, . . .n, such that AiAj = bjci −bicj for all i, j with 1 \leqi \leqj...

Practice › Mathematics › IMO Shortlist › IMO 2001 Shortlist ›

IMO 2001 SL G8

IMO 2001 SL G8 Origin: ISR | Category: Geometry Problem Let ABC be a triangle with ∡BAC = 60◦. Let AP bisect \angleBAC and let BQ bisect \angleABC, with P on BC and Q on AC. If AB + BP = AQ + QB, what are the angles of the triangle? Solution Let S and T respectively be the points on the extensions of AB and AQ over B and...

Practice › Mathematics › IMO Shortlist › IMO 2000 Shortlist ›

IMO 2000 SL G7

IMO 2000 SL G7 Origin: IRN | Category: Geometry Problem Ten gangsters are standing on a ﬂat surface, and the distances between them are all distinct. At twelve o’clock, when the church bells start chiming, each of them fatally shoots the one among the other nine gangsters who is the nearest. At least how many gangsters will be killed? Solution The problem can be reformulated in the following way: Given...

Practice › Mathematics › IMO Shortlist › IMO 1999 Shortlist ›

IMO 1999 SL G5

IMO 1999 SL G5 Origin: FRA | Category: Geometry Problem Let ABC be a triangle, Ωits incircle and Ωa, Ωb, Ωc three circles three circles orthogonal to Ωpassing through B and C, A and C, and A and B respectively. The circles Ωa, Ωb meet again in C′; in the same way we obtain the points B′ and A′. Prove that the radius of the circumcircle of A′B′C′ is half...

Practice › Mathematics › IMO Shortlist › IMO 1999 Shortlist ›

IMO 1999 SL G6

IMO 1999 SL G6 Origin: RUS | Category: Geometry Problem Two circles Ω1 and Ω2 touch internally the circle Ωin M and N, and the center of Ω2 is on Ω1. The common chord of the circles Ω1 and Ω2 intersects Ωin A and B. MA and MB intersect Ω1 in C and D. Prove that Ω2 is tangent to CD. Solution We ﬁrst introduce the following lemmas. Lemma 1....

Practice › Mathematics › IMO Shortlist › IMO 1996 Shortlist ›

IMO 1996 SL G8

IMO 1996 SL G8 Origin: RUS | Category: Geometry Problem Let $\triangle ABCD$ be a convex quadrilateral, and let $R_A$, $R_B$, $R_C$, and $R_D$ denote the circumradii of the triangles $\triangle DAB$, $\triangle ABC$, $\triangle BCD$, and $\triangle CDA$ respectively. Prove that $$R_A+R_C>R_B+R_D$$ if and only if $$\angle A+\angle C>\angle B+\angle D.$$ Solution Let the diagonals $AC$ and $BD$ meet at $X$. Either $\angle AXB$ or $\angle AXD$ is greater...

Practice › Mathematics › IMO Shortlist › IMO 2003 Shortlist ›

IMO 2003 SL G5

IMO 2003 SL G5 Origin: KOR | Category: Geometry Problem Let ABC be an isosceles triangle with AC = BC, whose incenter is I. Let P be a point on the circumcircle of the triangle AIB lying inside the triangle ABC. The lines through P parallel to CA and CB meet AB at D and E, respectively. The line through P parallel to AB meets CA and CB at F...

Practice › Mathematics › IMO Shortlist › IMO 1995 Shortlist ›

IMO 1995 SL G5

IMO 1995 SL G5 Origin: NZL | Category: Geometry Problem Let ABCDEF be a convex hexagon with AB = BC = CD, DE = EF = FA, and ∡BCD = ∡EFA = \pi/3 (that is, 60◦). Let G and H be two points interior to the hexagon such that angles AGB and DHE are both 2\pi/3 (that is, 120◦). Prove that AG + GB + GH + DH + HE...

Practice › Mathematics › IMO Shortlist › IMO 1994 Shortlist ›

IMO 1994 SL G5

IMO 1994 SL G5 Origin: CYP | Category: Geometry Problem A line l does not meet a circle \omega with center O. E is the point on l such that OE is perpendicular to l. M is any point on l other than E. The tangents from M to \omega touch it at A and B. C is the point on MA such that EC is perpendicular to MA. D...

Practice › Mathematics › IMO Shortlist › IMO 1996 Shortlist ›

IMO 1996 SL G1

IMO 1996 SL G1 Origin: GBR | Category: Geometry Problem Let $\triangle ABC$ have orthocenter $H$, and let $P$ be a point on its circumcircle, distinct from $A$, $B$, $C$. Let $E$ be the foot of the altitude from $B$, let $PAQB$ and $PARC$ be parallelograms, and let $AQ$ meet $HR$ in $X$. Prove that $EX\parallel AP$. Solution We first show that $H$ is the common orthocenter of the triangles...

Practice › Mathematics › IMO Shortlist › IMO 1995 Shortlist ›

IMO 1995 SL G8

IMO 1995 SL G8 Origin: COL | Category: Geometry Problem Let ABC be a triangle. A circle passing through B and C in- tersects the sides AB and AC again at C′ and B′, respectively. Prove that BB′, CC′, and HH′ are concurrent, where H and H′ are the orthocenters of triangles ABC and AB′C′ respectively. Solution Let BB′ cut CC′ at P. Since \angleB′BC′ = \angleB′CC′, it follows that...

Practice › Mathematics › IMO Shortlist › IMO 1996 Shortlist ›

IMO 1996 SL G5

IMO 1996 SL G5 Origin: ARM | Category: Geometry Problem Let $ABCDEF$ be a convex hexagon such that $AB \parallel DE$, $BC \parallel EF$, and $CD \parallel AF$. Let $R_A$, $R_C$, $R_E$ be the circumradii of triangles $FAB$, $BCD$, $DEF$ respectively, and let $P$ denote the perimeter of the hexagon. Prove that $$R_A + R_C + R_E \geq \frac{P}{2}.$$ Solution Let $a, b, c, d, e, f$ denote the lengths...

Practice › Mathematics › IMO Shortlist › IMO 2000 Shortlist ›

IMO 2000 SL G2

IMO 2000 SL G2 Origin: RUS | Category: Geometry Problem Two circles G1 and G2 intersect at M and N. Let AB be the line tangent to these circles at A and B, respectively, such that M lies closer to AB than N. Let CD be the line parallel to AB and passing through M, with C on G1 and D on G2. Lines AC and BD meet at E;...

Practice › Mathematics › IMO Shortlist › IMO 2003 Shortlist ›

IMO 2003 SL G7

IMO 2003 SL G7 Origin: SAF | Category: Geometry Problem Let ABC be a triangle with semiperimeter s and inradius r. The semicircles with diameters BC, CA, AB are drawn outside of the triangle ABC. The circle tangent to all three semicircles has radius t. Prove that s 2 < t \leqs 2 + 1 − \sqrt r. Solution Let D, E, F be the midpoints of BC, CA, AB,...

Practice › Mathematics › IMO Shortlist › IMO 2002 Shortlist ›

IMO 2002 SL G3

IMO 2002 SL G3 Origin: KOR | Category: Geometry Problem The circle S has center O, and BC is a diameter of S. Let A be a point of S such that ∡AOB < 120◦. Let D be the midpoint of the arc AB that does not contain C. The line through O parallel to DA meets the line AC at I. The perpendicular bisector of OA meets S at...

Practice › Mathematics › IMO Shortlist › IMO 2000 Shortlist ›

IMO 2000 SL G3

IMO 2000 SL G3 Origin: IND | Category: Geometry Problem Let O be the circumcenter and H the orthocenter of an acute triangle ABC. Show that there exist points D, E, and F on sides BC, CA, and AB respectively such that OD + DH = OE + EH = OF + FH and the lines AD, BE, and CF are concurrent. Solution Let L be the point symmetric to...

Practice › Mathematics › IMO Shortlist › IMO 2001 Shortlist ›

IMO 2001 SL G3

IMO 2001 SL G3 Origin: GBR | Category: Geometry Problem Let ABC be a triangle with centroid G. Determine, with proof, the position of the point P in the plane of ABC such that AP \cdot AG + BP \cdot BG + CP \cdot CG is a minimum, and express this minimum value in terms of the side lengths of ABC. Solution Let us investigate a more general problem, in...

Practice › Mathematics › IMO Shortlist › IMO 2002 Shortlist ›

IMO 2002 SL G2

IMO 2002 SL G2 Origin: KOR | Category: Geometry Problem Let ABC be a triangle for which there exists an interior point F such that \angleAFB = \angleBFC = \angleCFA. Let the lines BF and CF meet the sides AC and AB at D and E respectively. Prove that AB + AC \geq4DE. Solution Construct equilateral triangles ACP and ABQ outside the triangle ABC. Since \angleAPC + \angleAFC = 60◦+...

Practice › Mathematics › IMO Shortlist › IMO 1994 Shortlist ›

IMO 1994 SL G3

IMO 1994 SL G3 Origin: RUS | Category: Geometry Problem A circle \omega is tangent to two parallel lines l1 and l2. A second circle \omega1 is tangent to l1 at A and to \omega externally at C. A third circle \omega2 is tangent to l2 at B, to \omega externally at D, and to \omega1 externally at E. AD intersects BC at Q. Prove that Q is the circumcenter...

Practice › Mathematics › IMO Shortlist › IMO 2003 Shortlist ›

IMO 2003 SL G1

IMO 2003 SL G1 Origin: FIN | Category: Geometry Problem Let ABCD be a cyclic quadrilateral. Let P, Q, R be the feet of the perpendiculars from D to the lines BC, CA, AB, respectively. Show that PQ = QR if and only if the bisectors of \angleABC and \angleADC are concurrent with AC. Solution Denote by K and L the intersec- tions of the bisectors of \angleABC and \angleADC...

Practice › Mathematics › IMO Shortlist › IMO 1999 Shortlist ›

IMO 1999 SL G4

IMO 1999 SL G4 Origin: GBR | Category: Geometry Problem For a triangle T = ABC we take the point X on the side (AB) such that AX/XB = 4/5, the point Y on the segment (CX) such that CY = 2Y X, and, if possible, the point Z on the ray (CA such that ∡CXZ = 180◦−∡ABC. We denote by \Sigma the set of all triangles T for which...

Practice › Mathematics › IMO Shortlist › IMO 1995 Shortlist ›

IMO 1995 SL G3

IMO 1995 SL G3 Origin: TUR | Category: Geometry Problem The incircle of ABC touches BC, CA, and AB at D, E, and F respectively. X is a point inside ABC such that the incircle of XBC touches BC at D also, and touches CX and XB at Y and Z, respectively. Prove that EFZY is a cyclic quadrilateral. Solution If EF is parallel to BC, \triangleABC must be isosceles...

Practice › Mathematics › IMO Shortlist › IMO 1994 Shortlist ›

IMO 1994 SL G2

IMO 1994 SL G2 Origin: UKR | Category: Geometry Problem ABCD is a quadrilateral with BC parallel to AD. M is the midpoint of CD, P that of MA and Q that of MB. The lines DP and CQ meet at N. Prove that N is not outside triangle ABM.8 Solution Although it does not seem to have been noticed at the jury, the state- ment of the problem is...

Practice › Mathematics › IMO Shortlist › IMO 2003 Shortlist ›

IMO 2003 SL G6

IMO 2003 SL G6 Origin: POL | Category: Geometry Problem Each pair of opposite sides of a convex hexagon has the following property: The distance between their midpoints is equal to \sqrt 3/2 times the sum of their lengths. Prove that all the angles of the hexagon are equal. Solution Let ABCDEF be the given hexagon. We shall use the following lemma. Lemma. If \angleXZY \geq60◦and if M is the...

Practice › Mathematics › IMO Shortlist › IMO 2001 Shortlist ›

IMO 2001 SL G5

IMO 2001 SL G5 Origin: GRE | Category: Geometry Problem Let ABC be an acute triangle. Let DAC, EAB, and FBC be isosceles triangles exterior to ABC, with DA = DC, EA = EB, and FB = FC such that \angleADC = 2\angleBAC, \angleBEA = 2\angleABC, \angleCFB = 2\angleACB. Let D′ be the intersection of lines DB and EF, let E′ be the intersection of EC and DF, and let...

Practice › Mathematics › IMO Shortlist › IMO 1996 Shortlist ›

IMO 1996 SL G9

IMO 1996 SL G9 Origin: UKR | Category: Geometry Problem In the plane are given a point $O$ and a polygon $F$ (not necessarily convex). Let $P$ denote the perimeter of $F$, $D$ the sum of the distances from $O$ to the vertices of $F$, and $H$ the sum of the distances from $O$ to the lines containing the sides of $F$. Prove that $$D^2 - H^2 \geq \frac{P^2}{4}.$$ Solution...

Practice › Mathematics › IMO Shortlist › IMO 2000 Shortlist ›

IMO 2000 SL G1

IMO 2000 SL G1 Origin: NET | Category: Geometry Problem In the plane we are given two circles intersecting at X and Y . Prove that there exist four points A, B, C, D with the following property: For every circle touching the two given circles at A and B, and meeting the line XY at C and D, each of the lines AC, AD, BC, BD passes through one...

Practice › Mathematics › IMO Shortlist › IMO 1995 Shortlist ›

IMO 1995 SL G2

IMO 1995 SL G2 Origin: GER | Category: Geometry Problem Let A, B, and C be noncollinear points. Prove that there is a unique point X in the plane of ABC such that XA2 + XB2 + AB2 = XB2 + XC2 + BC2 = XC2 + XA2 + CA2. Solution Let A′, B′, C′ be the points symmetric to A, B, C with respect to the midpoints of BC,...

Practice › Mathematics › IMO Shortlist › IMO 2003 Shortlist ›

IMO 2003 SL G2

IMO 2003 SL G2 Origin: GRE | Category: Geometry Problem Three distinct points A, B, C are ﬁxed on a line in this order. Let \Gamma be a circle passing through A and C whose center does not lie on the line AC. Denote by P the intersection of the tangents to \Gamma at A and C. Suppose \Gamma meets the segment PB at Q. Prove that the intersection of...

Practice › Mathematics › IMO Shortlist › IMO 1995 Shortlist ›

IMO 1995 SL G1

IMO 1995 SL G1 Origin: BUL | Category: Geometry Problem Let A, B, C, and D be distinct points on a line, in that order. The circles with diameters AC and BD intersect at X and Y . O is an arbitrary point on the line XY but not on AD. CO intersects the circle with diameter AC again at M, and BO intersects the other circle again at N....

Practice › Mathematics › IMO Shortlist › IMO 2004 Shortlist ›

IMO 2004 SL G7

IMO 2004 SL G7 Origin: RUS | Category: Geometry Problem For a given triangle ABC, let X be a variable point on the line BC such that C lies between B and X and the incircles of the triangles ABX and ACX intersect at two distinct points P and Q. Prove that the line PQ passes through a point independent of X. Solution The proof uses the following observation: Lemma....

Practice › Mathematics › IMO Shortlist › IMO 1995 Shortlist ›

IMO 1995 SL G6

IMO 1995 SL G6 Origin: USA | Category: Geometry Problem Let A1A2A3A4 be a tetrahedron, G its centroid, and A′ 1, A′ 2, A′ 3, and A′ 4 the points where the circumsphere of A1A2A3A4 in- tersects GA1, GA2, GA3, and GA4, respectively. Prove that GA1 \cdot GA2 \cdot GA3 \cdot GA4 \leqGA′ 1 \cdot GA′ 2 \cdot GA′ 3 \cdot GA′ and GA′ + GA′ + GA′ + GA′...

Practice › Mathematics › IMO Shortlist › IMO 2002 Shortlist ›

IMO 2002 SL G1

IMO 2002 SL G1 Origin: FRA | Category: Geometry Problem Let B be a point on a circle S1, and let A be a point distinct from B on the tangent at B to S1. Let C be a point not on S1 such that the line segment AC meets S1 at two distinct points. Let S2 be the circle touching AC at C and touching S1 at a point...

Practice › Mathematics › IMO Shortlist › IMO 2002 Shortlist ›

IMO 2002 SL G6

IMO 2002 SL G6 Origin: UKR | Category: Geometry Problem Let n \geq3 be a positive integer. Let C1, C2, C3, . . . , Cn be unit circles in the plane, with centers O1, O2, O3, . . . , On respectively. If no line meets more than two of the circles, prove that 1\leqi<j\leqn OiOj \leq(n −1)\pi . Solution Let l(MN) denote the length of the shorter...

Practice › Mathematics › IMO Shortlist › IMO 1996 Shortlist ›

IMO 1996 SL G2

IMO 1996 SL G2 Origin: CAN | Category: Geometry Problem Let $P$ be a point inside $\triangle ABC$ such that $\angle APB - \angle C = \angle APC - \angle B.$ Let $D, E$ be the incenters of $\triangle APB$ and $\triangle APC$, respectively. Show that $AP$, $BD$, and $CE$ meet in a point. Solution Let $X, Y, Z$ respectively be the feet of the perpendiculars from $P$ to $BC$,...

Practice › Mathematics › IMO Shortlist › IMO 1994 Shortlist ›

IMO 1994 SL G1

IMO 1994 SL G1 Origin: FRA | Category: Geometry Problem A semicircle \Gamma is drawn on one side of a straight line l. C and D are points on \Gamma. The tangents to \Gamma at C and D meet l at B and A respectively, with the center of the semicircle between them. Let E be the point of intersection of AC and BD, and F the point on l...

Practice › Mathematics › IMO Shortlist › IMO 2002 Shortlist ›

IMO 2002 SL G5

IMO 2002 SL G5 Origin: AUS | Category: Geometry Problem For any set S of ﬁve points in the plane, no three of which are collinear, let M(S) and m(S) denote the greatest and smallest areas, respectively, of triangles determined by three points from S. What is the minimum possible value of M(S)/m(S)? Solution When S is the set of vertices of a regular pentagon, then it is easily veriﬁed...

Practice › Mathematics › IMO Shortlist › IMO 1996 Shortlist ›

IMO 1996 SL G6

IMO 1996 SL G6 Origin: ARM | Category: Geometry Problem Let the sides of two rectangles be ${a, b}$ and ${c, d}$ with $a < c \leq d < b$ and $ab < cd$. Prove that the first rectangle can be placed within the second one if and only if $(b^2 - a^2)^2 \leq (bd - ac)^2 + (bc - ad)^2.$ Solution Denote by $ABCD$ and $EFGH$ the two rectangles,...

Practice › Mathematics › IMO Shortlist › IMO 1999 Shortlist ›

IMO 1999 SL G3

IMO 1999 SL G3 Origin: EST | Category: Geometry Problem A set S of points in space will be called completely sym- metric if it has at least three elements and satisﬁes the following condition: For every two distinct points A, B from S the perpendicular bisector of the segment AB is an axis of symmetry for S. Prove that if a completely symmetric set is ﬁnite, then it consists...

Practice › Mathematics › IMO Shortlist › IMO 2004 Shortlist ›

IMO 2004 SL G3

IMO 2004 SL G3 Origin: KOR | Category: Geometry Problem Let O be the circumcenter of an acute-angled triangle ABC with \angleB < \angleC. The line AO meets the side BC at D. The circumcenters of the triangles ABD and ACD are E and F, respectively. Extend the sides BA and CA beyond A, and choose on the respective extension points G and H such that AG = AC and...

Practice › Mathematics › IMO Shortlist › IMO 2004 Shortlist ›

IMO 2004 SL G4

IMO 2004 SL G4 Origin: POL | Category: Geometry Problem In a convex quadrilateral ABCD the diagonal BD does not bisect the angles ABC and CDA. The point P lies inside ABCD and satisﬁes \anglePBC = \angleDBA and \anglePDC = \angleBDA. Prove that ABCD is a cyclic quadrilateral if and only if AP = CP. Solution Assume ﬁrst that the points A, B, C, D are concyclic. Let the lines...

Practice › Mathematics › IMO Shortlist › IMO 2001 Shortlist ›

IMO 2001 SL G6

IMO 2001 SL G6 Origin: IND | Category: Geometry Problem Let ABC be a triangle and P an exterior point in the plane of the triangle. Suppose AP, BP, CP meet the sides BC, CA, AB (or ex- tensions thereof) in D, E, F, respectively. Suppose further that the areas of triangles PBD, PCE, PAF are all equal. Prove that each of these areas is equal to the area of...

Practice › Mathematics › IMO Shortlist › IMO 2003 Shortlist ›

IMO 2003 SL G3

IMO 2003 SL G3 Origin: IND | Category: Geometry Problem Let ABC be a triangle and let P be a point in its interior. Denote by D, E, F the feet of the perpendiculars from P to the lines BC, CA, and AB, respectively. Suppose that AP 2 + PD2 = BP 2 + PE2 = CP 2 + PF 2. Denote by IA, IB, IC the excenters of the...

Practice › Mathematics › IMO Shortlist › IMO 2004 Shortlist ›

IMO 2004 SL G1

IMO 2004 SL G1 Origin: ROM | Category: Geometry Problem Let ABC be an acute-angled triangle with AB ̸= AC. The circle with diameter BC intersects the sides AB and AC at M and N, respectively. Denote by O the midpoint of BC. The bisectors of the angles BAC and MON intersect at R. Prove that the circumcircles of the triangles BMR and CNR have a common point lying on...

Practice › Mathematics › IMO Shortlist › IMO 1995 Shortlist ›

IMO 1995 SL G7

IMO 1995 SL G7 Origin: LAT | Category: Geometry Problem O is a point inside a convex quadrilateral ABCD of area S. K, L, M, and N are interior points of the sides AB, BC, CD, and DA respectively. If OKBL and OMDN are parallelograms, prove that \sqrt S \geq\sqrtS1 + \sqrtS2, where S1 and S2 are the areas of ONAK and OLCM respectively. Solution If O lies on AC,...

Practice › Mathematics › IMO Shortlist › IMO 2004 Shortlist ›

IMO 2004 SL G6

IMO 2004 SL G6 Origin: GBR | Category: Geometry Problem Let P be a convex polygon. Prove that there is a convex hexagon that is contained in P and that occupies at least 75 percent of the area of P. Solution Let ABC be the triangle of maximum area S contained in P (it exists because of compactness of P). Draw parallels to BC, CA, AB through A, B, C,...

Practice › Mathematics › IMO Shortlist › IMO 2001 Shortlist ›

IMO 2001 SL G2

IMO 2001 SL G2 Origin: KOR | Category: Geometry Problem In acute triangle ABC with circumcenter O and altitude AP, ∡C \geq∡B + 30◦. Prove that ∡A + ∡COP < 90◦. Solution Since \angleOCP = 90◦−\angleA, we are led to showing that \angleOCP > \angleCOP, i.e., OP > CP. By the triangle inequality it suﬃces to prove CP < 1 2CO. Let CO = R. The law of sines yields...

Practice › Mathematics › IMO Shortlist › IMO 1999 Shortlist ›

IMO 1999 SL G8

IMO 1999 SL G8 Origin: RUS | Category: Geometry Problem Points A, B, C divide the circumcircle Ωof the triangle ABC into three arcs. Let X be a variable point on the arc AB, and let O1, O2 be the incenters of the triangles CAX and CBX. Prove that the circumcircle of the triangle XO1O2 intersects Ωin a ﬁxed point. Solution We ﬁrst introduce the same lemma as in problem...

Practice › Mathematics › IMO Shortlist › IMO 1995 Shortlist ›

IMO 1995 SL G4

IMO 1995 SL G4 Origin: UKR | Category: Geometry Problem An acute triangle ABC is given. Points A1 and A2 are taken on the side BC (with A2 between A1 and C), B1 and B2 on the side AC (with B2 between B1 and A), and C1 and C2 on the side AB (with C2 between C1 and B) such that \angleAA1A2 = \angleAA2A1 = \angleBB1B2 = \angleBB2B1 = \angleCC1C2...

Practice › Mathematics › IMO Shortlist › IMO 2001 Shortlist ›

IMO 2001 SL G4

IMO 2001 SL G4 Origin: FRA | Category: Geometry Problem Let M be a point in the interior of triangle ABC. Let A′ lie on BC with MA′ perpendicular to BC. Deﬁne B′ on CA and C′ on AB similarly. Deﬁne p(M) = MA′ \cdot MB′ \cdot MC′ MA \cdot MB \cdot MC . Determine, with proof, the location of M such that p(M) is maximal. Let µ(ABC) denote the...

Practice › Mathematics › IMO Shortlist › IMO 1999 Shortlist ›

IMO 1999 SL G2

IMO 1999 SL G2 Origin: JAP | Category: Geometry Problem A circle is called a separator for a set of ﬁve points in a plane if it passes through three of these points, it contains a fourth point in its interior, and the ﬁfth point is outside the circle. Prove that every set of ﬁve points such that no three are collinear and no four are concyclic has exactly four...

Practice › Mathematics › IMO Shortlist › IMO 2000 Shortlist ›

IMO 2000 SL G6

IMO 2000 SL G6 Origin: ARG | Category: Geometry Problem Let ABCD be a convex quadrilateral with AB not parallel to CD, let X be a point inside ABCD such that ∡ADX = ∡BCX < 90◦ and ∡DAX = ∡CBX < 90◦. If Y is the point of intersection of the perpendicular bisectors of AB and CD, prove that ∡AY B = 2∡ADX. Solution By the condition of the problem,...

Practice › Mathematics › IMO Shortlist › IMO 2001 Shortlist ›

IMO 2001 SL G1

IMO 2001 SL G1 Origin: UKR | Category: Geometry Problem Let A1 be the center of the square inscribed in acute triangle ABC with two vertices of the square on side BC. Thus one of the two re- maining vertices of the square is on side AB and the other is on AC. Points B1, C1 are deﬁned in a similar way for inscribed squares with two vertices on sides...

Practice › Mathematics › IMO Shortlist › IMO 2004 Shortlist ›

IMO 2004 SL G8

IMO 2004 SL G8 Origin: SMN | Category: Geometry Problem A cyclic quadrilateral ABCD is given. The lines AD and BC intersect at E, with C between B and E; the diagonals AC and BD intersect at F. Let M be the midpoint of the side CD, and let N ̸= M be a point on the circumcircle of the triangle ABM such that AN/BN = AM/BM. Prove that the...

Practice › Mathematics › IMO Shortlist › IMO 2001 Shortlist ›

IMO 2001 SL G7

IMO 2001 SL G7 Origin: BUL | Category: Geometry Problem Let O be an interior point of acute triangle ABC. Let A1 lie on BC with OA1 perpendicular to BC. Deﬁne B1 on CA and C1 on AB similarly. Prove that O is the circumcenter of ABC if and only if the perimeter of A1B1C1 is not less than any one of the perimeters of AB1C1, BC1A1, and CA1B1. Solution...

Practice › Mathematics › IMO Shortlist › IMO 1999 Shortlist ›

IMO 1999 SL G1

IMO 1999 SL G1 Origin: ARM | Category: Geometry Problem Let ABC be a triangle and M an interior point. Prove that min{MA, MB, MC} + MA + MB + MC < AB + AC + BC. Solution We use the following simple lemma. Lemma. Suppose that M is the interior point of a convex quadrilateral ABCD. Then it follows that MA + MB < AD + DC + CB....

Practice › Mathematics › IMO Shortlist › IMO 2004 Shortlist ›

IMO 2004 SL G2

IMO 2004 SL G2 Origin: KAZ | Category: Geometry Problem The circle \Gamma and the line ℓdo not intersect. Let AB be the diameter of \Gamma perpendicular to ℓ, with B closer to ℓthan A. An arbitrary point C ̸= A, B is chosen on \Gamma. The line AC intersects ℓat D. The line DE is tangent to \Gamma at E, with B and E on the same side of...

Practice › Mathematics › IMO Shortlist › IMO 2002 Shortlist ›

IMO 2002 SL G7

IMO 2002 SL G7 Origin: BUL | Category: Geometry Problem The incircle Ωof the acute-angled triangle ABC is tangent to BC at K. Let AD be an altitude of triangle ABC and let M be the midpoint of AD. If N is the other common point of Ωand KM, prove that Ωand the circumcircle of triangle BCN are tangent at N. Solution Let k be the circle through B, C...

Practice › Mathematics › IMO Shortlist › IMO 1999 Shortlist ›

IMO 1999 SL G7

IMO 1999 SL G7 Origin: ARM | Category: Geometry Problem The point M inside the convex quadrilateral ABCD is such that MA = MC, \angleAMB = \angleMAD+\angleMCD, \angleCMD = \angleMCB+\angleMAB. Prove that AB \cdot CM = BC \cdot MD and BM \cdot AD = MA \cdot CD. Solution Let us construct a convex quadrilateral PQRS and an interior point T such that \trianglePTQ ∼= \triangleAMB, \triangleQTR ∼\triangleAMD, and \trianglePTS ∼\triangleCMD....

Practice › Mathematics › IMO Shortlist › IMO 1996 Shortlist ›

IMO 1996 SL G7

IMO 1996 SL G7 Origin: GBR | Category: Geometry Problem Let $\triangle ABC$ be an acute-angled triangle with circumcenter $O$ and circumradius $R$. Let $AO$ meet the circle $BOC$ again in $A'$, let $BO$ meet the circle $COA$ again in $B'$, and let $CO$ meet the circle $AOB$ again in $C'$. Prove that $$OA' \cdot OB' \cdot OC' \geq 8R^3.$$ When does equality hold? Solution Let $A_1$ be the point...

Practice › Mathematics › IMO Shortlist › IMO 2003 Shortlist ›

IMO 2003 SL G4

IMO 2003 SL G4 Origin: ARM | Category: Geometry Problem Let \Gamma1, \Gamma2, \Gamma3, \Gamma4 be distinct circles such that \Gamma1, \Gamma3 are externally tangent at P, and \Gamma2, \Gamma4 are externally tangent at the same point P. Suppose that \Gamma1 and \Gamma2; \Gamma2 and \Gamma3; \Gamma3 and \Gamma4; \Gamma4 and \Gamma1 meet at A, B, C, D, respectively, and that all these points are diﬀerent from P. Prove that...

Practice › Mathematics › IMO Shortlist › IMO 2004 Shortlist ›

IMO 2004 SL G5

IMO 2004 SL G5 Origin: SMN | Category: Geometry Problem Let A1A2 . . . An be a regular n-gon. The points B1, . . . , Bn−1 are deﬁned as follows: (i) If i = 1 or i = n −1, then Bi is the midpoint of the side AiAi+1. (ii) If i ̸= 1, i ̸= n −1, and S is the intersection point of A1Ai+1 and AnAi,...

Practice › Mathematics › IMO Shortlist › IMO 2000 Shortlist ›

IMO 2000 SL G8

IMO 2000 SL G8 Origin: RUS | Category: Geometry Problem A1A2A3 is an acute-angled triangle. The foot of the altitude from Ai is Ki, and the incircle touches the side opposite Ai at Li. The line K1K2 is reﬂected in the line L1L2. Similarly, the line K2K3 is reﬂected in L2L3, and K3K1 is reﬂected in L3L1. Show that the three new lines form a triangle with vertices on the...

Practice › Mathematics › IMO Shortlist › IMO 2000 Shortlist ›

IMO 2000 SL G5

IMO 2000 SL G5 Origin: GBR | Category: Geometry Problem The tangents at B and A to the circumcircle of an acute- angled triangle ABC meet the tangent at C at T and U respectively. AT meets BC at P, and Q is the midpoint of AP; BU meets CA at R, and S is the midpoint of BR. Prove that \angleABQ = \angleBAS. Determine, in terms of ratios of...

Practice › Mathematics › IMO Shortlist › IMO 1994 Shortlist ›

IMO 1994 SL G4

IMO 1994 SL G4 Origin: AUS-ARM | Category: Geometry Problem N is an arbitrary point on the bisector of \angleBAC. P and O are points on the lines AB and AN, respectively, such that ∡ANP = 90◦= ∡APO. Q is an arbitrary point on NP, and an arbitrary line through Q meets the lines AB and AC at E and F respectively. Prove that ∡OQE = 90◦if and only if...

Practice › Mathematics › IMO Shortlist › IMO 2002 Shortlist ›

IMO 2002 SL G8

IMO 2002 SL G8 Origin: ARM | Category: Geometry Problem Let S1 and S2 be circles meeting at the points A and B. A line through A meets S1 at C and S2 at D. Points M, N, K lie on the line segments CD, BC, BD respectively, with MN parallel to BD and MK parallel to BC. Let E and F be points on those arcs BC of S1...

Practice › Mathematics › IMO Shortlist › IMO 2002 Shortlist ›

IMO 2002 SL G4

IMO 2002 SL G4 Origin: RUS | Category: Geometry Problem Circles S1 and S2 intersect at points P and Q. Distinct points A1 and B1 (not at P or Q) are selected on S1. The lines A1P and B1P meet S2 again at A2 and B2 respectively, and the lines A1B1 and A2B2 meet at C. Prove that as A1 and B1 vary, the circumcenters of triangles A1A2C all lie...

Practice › Mathematics › IMO Shortlist › IMO 1996 Shortlist ›

IMO 1996 SL G3

IMO 1996 SL G3 Origin: GBR | Category: Geometry Problem Let $\triangle ABC$ be an acute-angled triangle with $BC > CA$. Let $O$ be the circumcenter, $H$ its orthocenter, and $F$ the foot of its altitude $CH$. Let the perpendicular to $OF$ at $F$ meet the side $CA$ at $P$. Prove that $\angle FHP = \angle BAC.$ Possible second part: What happens if $|BC| \leq |CA|$ (the triangle still being...

Practice › Mathematics › IMO Shortlist › IMO 1996 Shortlist ›

IMO 1996 SL G4

IMO 1996 SL G4 Origin: USA | Category: Geometry Problem Let $\triangle ABC$ be an equilateral triangle and let $P$ be a point in its interior. Let the lines $AP$, $BP$, $CP$ meet the sides $BC$, $CA$, $AB$ in the points $A_1$, $B_1$, $C_1$ respectively. Prove that $$A_1B_1 \cdot B_1C_1 \cdot C_1A_1 \geq A_1B \cdot B_1C \cdot C_1A.$$ Solution By the law of cosines applied to $\triangle CA_1B_1$, we obtain...

Practice › Codeforces Solutions › Codeforces Round 131 (Div. 1) ›

CF 213D - Stars

CF 213D - Stars Rating: 2300 Tags: constructive algorithms, geometry Solve time: 1m 36s Verified: no Solution Problem Understanding We must construct n pentagram-shaped stars in the plane. Each star comes from a regular pentagon with side length 10 , and the painted segments are exactly its five diagonals. The output is not just geometry. We also need a valid drawing order. Rubik starts with the pen touching the paper,...

Practice › Codeforces Solutions › April Fools Day Contest 2014 ›

CF 409G - On a plane

CF 409G - On a plane Rating: 2200 Tags: *special, geometry Solve time: 1m 53s Verified: no Solution Problem Understanding We are given a set of points on a two-dimensional plane, each with real-valued coordinates. The task is to find the largest possible angle formed at the origin by any three of these points, where the origin serves as the vertex and the rays extend to the selected points. The...

Practice › Codeforces Solutions › CROC-MBTU 2012, Final Round (Online version, Div. 2) ›

CF 250D - Building Bridge

CF 250D - Building Bridge Rating: 1900 Tags: geometry, ternary search, two pointers Solve time: 1m 13s Verified: yes Solution Problem Understanding We are choosing a path from a western village at the origin to a river bank located at a vertical line $x = a$, then crossing the river in a straight line to another point on the eastern bank $x = b$, and finally following a pre-determined path...

Practice › Codeforces Solutions ›

Codeforces Round 189 (Div. 1)

Codeforces Round 189 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 1/2 | Rating range: 2100-3000 | Time: 4m 42s Problem Name Rating Tags Solve Time Verified C Kalila and Dimna in the Logging Industry 2100 dp, geometry 2m 47s ✗ E Ping-Pong 3000 data-structures 1m 55s ✓

Practice › Codeforces Solutions › Codeforces Round 102 (Div. 1) ›

CF 142E - Help Greg the Dwarf 2

CF 142E - Help Greg the Dwarf 2 Rating: 3000 Tags: geometry Solve time: 5m 46s Verified: yes Solution Problem Understanding We are asked to find the shortest distance between two points on a cone, where the cone has a circular base of radius r and height h , and the points may lie anywhere on the cone's lateral surface or the base. The input gives us the coordinates of...

Practice › Codeforces Solutions › Codeforces Round 100 ›

CF 140A - New Year Table

CF 140A - New Year Table Rating: 1700 Tags: geometry, math Solve time: 1m 45s Verified: yes Solution Problem Understanding We have a large circular table with radius R and want to place n identical circular plates, each with radius r . Every plate must satisfy three conditions simultaneously. First, the entire plate must stay inside the table. Second, every plate must touch the boundary of the table. Third, no...

Practice › Codeforces Solutions › Codeforces Round 125 (Div. 2) ›

CF 199B - Special Olympics

CF 199B - Special Olympics Rating: 1900 Tags: geometry Solve time: 1m 35s Verified: no Solution Problem Understanding We are asked to count the number of distinct circular contours that can be formed on a plane where two black-painted rings are placed. Each ring is defined by two concentric circles, an inner radius and an outer radius. The centers of the rings are different, and the rings can partially overlap...

Practice › Codeforces Solutions › Codeforces Round 128 (Div. 2) ›

CF 203D - Hit Ball

CF 203D - Hit Ball Rating: 1700 Tags: geometry, implementation, math Solve time: 1m 20s Verified: no Solution Problem Understanding We are asked to simulate a three-dimensional billiard-like scenario where a ball travels inside a rectangular corridor with perfectly reflecting walls, floor, and ceiling. The corridor is infinite in the y direction, and the ball is initially placed at the center of the corridor, at a distance m from the...

Practice › Codeforces Solutions ›

Codeforces Round 159 (Div. 2)

Codeforces Round 159 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 4/4 | Rating range: 1100-1900 | Time: 6m 19s Problem Name Rating Tags Solve Time Verified A Sockets 1100 greedy, implementation, sortings 1m 10s ✓ B Playing Cubes 1300 games, greedy, implementation 1m 23s ✓ C View Angle 1800 brute-force, geometry, math 2m 43s ✓ D Sum 1900 greedy, math 1m 3s ✓

Practice › Codeforces Solutions ›

CROC-MBTU 2012, Final Round (Online version, Div. 2)

CROC-MBTU 2012, Final Round (Online version, Div. 2) Type: Div. 2 | Problems: 5 | Verified: 2/5 | Rating range: 1000-2000 | Time: 11m 54s Problem Name Rating Tags Solve Time Verified A Paper Work 1000 greedy 3m 9s ✗ B Restoring IPv6 1500 implementation, strings 1m 5s ✓ C Movie Critics 1600 greedy 3m 12s ✗ D Building Bridge 1900 geometry, ternary-search, two-pointers 1m 13s ✓ E Mad Joe...

Practice › Codeforces Solutions › Codeforces Round 171 (Div. 2) ›

CF 279A - Point on Spiral

CF 279A - Point on Spiral Rating: 1400 Tags: brute force, geometry, implementation Solve time: 1m 28s Verified: yes Solution Problem Understanding The spiral starts at the origin and grows outward by alternating directions: right, up, left, down. Each new segment is longer than the previous pair. The first few moves are: right 1 up 1 left 2 down 2 right 3 up 3 and so on forever. We are...

Practice › Codeforces Solutions › Codeforces Round 113 (Div. 2) ›

CF 166B - Polygons

CF 166B - Polygons Rating: 2100 Tags: geometry, sortings Solve time: 3m 7s Verified: yes Solution Problem Understanding We are asked to determine whether one polygon is completely contained inside another. Polygon A is strictly convex, meaning all internal angles are less than 180 degrees and no three consecutive points are collinear. Polygon B is arbitrary but simple, meaning it does not intersect itself or touch itself. Both polygons are...

Practice › Codeforces Solutions ›

Croc Champ 2012 - Final

Croc Champ 2012 - Final Type: Special | Problems: 5 | Verified: 5/5 | Rating range: 1700-2900 | Time: 10m 12s Problem Name Rating Tags Solve Time Verified A Headquarters 1700 constructive-algorithms, math 1m 52s ✓ B Zoo 1700 brute-force, geometry 1m 27s ✓ C Cyclic Coloring 2200 dfs-and-similar 3m 32s ✓ D T-shirt 2700 dp, greedy, probabilities 1m 15s ✓ E Candy Shop 2900 greedy 2m 6s ✓

Practice › Codeforces Solutions ›

Codeforces Round 152 (Div. 1)

Codeforces Round 152 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 0/2 | Rating range: 2600-2700 | Time: 5m 24s Problem Name Rating Tags Solve Time Verified D Donkey and Stars 2700 data-structures, dp, geometry 1m 56s ✗ E Endless Matrix 2600 math 3m 28s ✗

Practice › Codeforces Solutions › Codeforces Round 120 (Div. 2) ›

CF 190B - Surrounded

CF 190B - Surrounded Rating: 1800 Tags: geometry Solve time: 1m 34s Verified: yes Solution Problem Understanding We are given two circles on the plane. Each circle represents an enemy ring surrounding a city. A radar can be placed at any point, and it detects everything within distance r from its position. The radar must be able to detect at least one point from each circle. We want the smallest...

Practice › Codeforces Solutions › Codeforces Round 238 (Div. 1) ›

CF 406D - Hill Climbing

CF 406D - Hill Climbing Rating: 2200 Tags: dfs and similar, geometry, trees Solve time: 2m 13s Verified: no Solution Problem Understanding We are given a sequence of hills placed along a line. Each hill has a fixed horizontal position and a height, and we imagine it as a vertical segment rising from the ground. From the top of a hill, you can “see” another hill if the straight segment...

Practice › LeetCode › LeetCode 22xx ›

LeetCode 2249 - Count Lattice Points Inside a Circle

LeetCode Problem 2249 Difficulty: 🟡 Medium Topics: Array, Hash Table, Math, Geometry, Enumeration Solution Problem Understanding The problem asks us to determine how many lattice points lie inside at least one of a set of circles on a 2D grid. Each circle is represented by a triplet [xi, yi, ri] , where (xi, yi) is the circle's center and ri is its radius. A lattice point is any point on...

Practice › Codeforces Solutions ›

Codeforces Round 152 (Div. 2)

Codeforces Round 152 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 800-2600 | Time: 11m 52s Problem Name Rating Tags Solve Time Verified A Cupboards 800 implementation 1m 34s ✓ B Chilly Willy 1400 math, number-theory 2m 53s ✓ C Robo-Footballer 2000 binary-search, geometry 2m ✗ D Sweets for Everyone! 2300 binary-search, greedy, implementation 3m 8s ✓ E Piglet's Birthday 2600 dp, math, probabilities...

Practice › Codeforces Solutions ›

Croc Champ 2012 - Round 2 (Unofficial Div. 2 Edition)

Croc Champ 2012 - Round 2 (Unofficial Div. 2 Edition) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 800-1300 | Time: 4m 22s Problem Name Rating Tags Solve Time Verified A Series of Crimes 800 brute-force, geometry, implementation 2m 48s ✓ B Number of Triplets 1300 binary-search, brute-force 1m 34s ✓

Practice › Codeforces Solutions › Codeforces Round 138 (Div. 2) ›

CF 224A - Parallelepiped

CF 224A - Parallelepiped Rating: 1100 Tags: brute force, geometry, math Solve time: 1m 1s Verified: yes Solution Problem Understanding We are given three positive integers representing the areas of three faces of a rectangular parallelepiped that meet at a single vertex. Each area corresponds to the product of two edge lengths: one face is the product of edges $a$ and $b$, another $b$ and $c$, and the third $a$...

Practice › Codeforces Solutions › Croc Champ 2012 - Final ›

CF 183B - Zoo

CF 183B - Zoo Rating: 1700 Tags: brute force, geometry Solve time: 1m 27s Verified: yes Solution Problem Understanding We are asked to maximize the total number of flamingos that can be observed from a row of binoculars on the x-axis. Each binocular sits at position (i,0) and can be aimed in any direction. Each flamingo is located somewhere in the first quadrant at integer coordinates (xᵢ, yᵢ). Once a...

Practice › Codeforces Solutions › Codeforces Round 110 (Div. 2) ›

CF 157B - Trace

CF 157B - Trace Rating: 1000 Tags: geometry, sortings Solve time: 2m 19s Verified: yes Solution Problem Understanding The problem presents a scenario where a wall is decorated with multiple concentric circles, some of which are painted red while others are blue in an alternating pattern. The outermost area beyond the largest circle is always blue. The task is to calculate the total area of all red-painted regions on this...

Practice › Codeforces Solutions ›

Codeforces Round 100

Codeforces Round 100 Type: Special | Problems: 6 | Verified: 3/6 | Rating range: 1700-2600 | Time: 12m 15s Problem Name Rating Tags Solve Time Verified A New Year Table 1700 geometry, math 1m 45s ✓ B New Year Cards 1800 brute-force, greedy, implementation 2m 41s ✗ C New Year Snowmen 1800 binary-search, data-structures, greedy 2m ✗ D New Year Contest 1800 greedy, sortings 1m 55s ✓ E New Year...

Practice › LeetCode › LeetCode 31xx ›

LeetCode 3102 - Minimize Manhattan Distances

LeetCode Problem 3102 Difficulty: 🔴 Hard Topics: Array, Math, Geometry, Sorting, Ordered Set Solution Problem Understanding The problem asks us to minimize the maximum Manhattan distance between any two points on a 2D plane after removing exactly one point from the input list. The input points is an array of integer coordinates [[x1, y1], [x2, y2], ..., [xn, yn]] . The Manhattan distance between two points (x1, y1) and (x2,...

Practice › Codeforces Solutions › Codeforces Round 101 (Div. 2) ›

CF 141B - Hopscotch

CF 141B - Hopscotch Rating: 1400 Tags: geometry, math Solve time: 1m 26s Verified: yes Solution Problem Understanding We are asked to determine whether a stone thrown onto a hopscotch court lands strictly inside a square, and if so, to identify which square. The court is constructed from squares of side length a , arranged in rows with a repeating 1-1-2-1-2 pattern. Each square is numbered sequentially starting from the...

Practice › Codeforces Solutions ›

Codeforces Round 120 (Div. 2)

Codeforces Round 120 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 4/4 | Rating range: 1100-1900 | Time: 6m 10s Problem Name Rating Tags Solve Time Verified A Vasya and the Bus 1100 greedy, math 1m 11s ✓ B Surrounded 1800 geometry 1m 34s ✓ C STL 1500 dfs-and-similar 1m 49s ✓ D Non-Secret Cypher 1900 two-pointers 1m 36s ✓

Practice › Codeforces Solutions › Codeforces Round 187 (Div. 1) ›

CF 314D - Sereja and Straight Lines

CF 314D - Sereja and Straight Lines Rating: 2500 Tags: binary search, data structures, geometry, sortings, two pointers Solve time: 1m 45s Verified: yes Solution Problem Understanding We are given a set of points in the plane, and we want to place two infinite straight lines that must always be perpendicular to each other. One of these lines is constrained in orientation: it must make a 45-degree angle with the...

Practice › Codeforces Solutions ›

Codeforces Round 123 (Div. 2)

Codeforces Round 123 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 3/4 | Rating range: 1000-2000 | Time: 5m 40s Problem Name Rating Tags Solve Time Verified A Let's Watch Football 1000 binary-search, brute-force, math 1m 24s ✓ C Try and Catch 1800 expression-parsing, implementation 1m 8s ✓ D Analyzing Polyline 1900 geometry, math, sortings 1m 28s ✗ E Building Forest 2000 data-structures, dsu, graphs 1m 40s ✓

Practice › Codeforces Solutions › Codeforces Round 165 (Div. 1) ›

CF 269E - String Theory

CF 269E - String Theory Rating: 3100 Tags: geometry, math, strings Solve time: 1m 58s Verified: no Solution Problem Understanding We are given a rectangular harp represented as a grid of size n × m , where pins are placed along the edges: n pins on the left and right sides, and m pins on the top and bottom sides. Each string connects exactly two pins located on different sides...

Practice › LeetCode › LeetCode 33xx ›

LeetCode 3380 - Maximum Area Rectangle With Point Constraints I

LeetCode Problem 3380 Difficulty: 🟡 Medium Topics: Array, Math, Binary Indexed Tree, Segment Tree, Geometry, Sorting, Enumeration Solution LeetCode 3380 - Maximum Area Rectangle With Point Constraints I Problem Understanding The problem gives us a set of unique points on a 2D plane. We need to determine the largest possible axis-aligned rectangle that can be formed using exactly four of those points as its corners. An axis-aligned rectangle means: The...

Practice › Codeforces Solutions ›

Codeforces Round 136 (Div. 1)

Codeforces Round 136 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 3/4 | Rating range: 1300-2500 | Time: 8m 14s Problem Name Rating Tags Solve Time Verified A Little Elephant and Problem 1300 implementation, sortings 2m 48s ✓ B Little Elephant and Array 1800 constructive-algorithms, data-structures 1m 7s ✓ C Little Elephant and Shifts 2100 data-structures 1m 54s ✓ D Little Elephant and Triangle 2500 geometry, math 2m...

Practice › Codeforces Solutions › Coder-Strike 2014 - Finals (online edition, Div. 1) ›

CF 420E - Playing the ball

CF 420E - Playing the ball Rating: 2600 Tags: geometry Solve time: 2m Verified: yes Solution Problem Understanding A ball is thrown from the origin along some chosen direction, and it repeatedly appears at equally spaced points along that ray: first at distance $d$, then at $2d$, then $3d$, and so on. The direction is fixed once chosen, but it can be any real direction in the plane. On the...

Practice › LeetCode › LeetCode 19xx ›

LeetCode 1924 - Erect the Fence II

LeetCode Problem 1924 Difficulty: 🔴 Hard Topics: Array, Math, Geometry Solution Here is a fully detailed technical solution guide for LeetCode 1924 - Erect the Fence II , following your formatting instructions: Problem Understanding The problem asks us to compute the minimum enclosing circle for a set of points in 2D space, where each point represents a tree. We are given a list of trees as coordinates trees[i] = [xi,...

Practice › LeetCode › LeetCode 21xx ›

LeetCode 2101 - Detonate the Maximum Bombs

LeetCode Problem 2101 Difficulty: 🟡 Medium Topics: Array, Math, Depth-First Search, Breadth-First Search, Graph Theory, Geometry Solution Problem Understanding In this problem, each bomb is represented by three integers: its x-coordinate, y-coordinate, and explosion radius. If a bomb explodes, every other bomb whose center lies within or on the boundary of that radius will also explode. Those newly exploded bombs can continue triggering additional bombs, creating a chain reaction. The...

Practice › Codeforces Solutions › Croc Champ 2013 - Finals (online version, Div. 1) ›

CF 309D - Tennis Rackets

CF 309D - Tennis Rackets Rating: 2700 Tags: brute force, geometry Solve time: 1m 52s Verified: yes Solution Problem Understanding We are asked to count the number of obtuse triangles that can be formed on a triangular tennis racket with evenly spaced holes along its sides. Each side has n holes dividing it into n+1 equal segments. The m holes nearest each vertex are reserved for ventilation and cannot be...

Practice › Codeforces Solutions ›

Codeforces Round 131 (Div. 1)

Codeforces Round 131 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1700-2700 | Time: 7m 23s Problem Name Rating Tags Solve Time Verified A Game 1700 dfs-and-similar, greedy 52s ✓ B Numbers 1900 combinatorics, dp 54s ✗ C Relay Race 2000 dp 2m 58s ✓ D Stars 2300 constructive-algorithms, geometry 1m 36s ✗ E Two Permutations 2700 data-structures, hashing, strings 1m 3s ✓

Practice › Codeforces Solutions ›

Codeforces Round 165 (Div. 2)

Codeforces Round 165 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 1100-1400 | Time: 3m 31s Problem Name Rating Tags Solve Time Verified A Fancy Fence 1100 geometry, implementation, math 1m 12s ✓ B Multithreading 1400 data-structures, greedy, implementation 2m 19s ✓

Practice › LeetCode › LeetCode 18xx ›

LeetCode 1828 - Queries on Number of Points Inside a Circle

LeetCode Problem 1828 Difficulty: 🟡 Medium Topics: Array, Math, Geometry Solution Problem Understanding This problem gives us two collections of geometric objects on a 2D plane. The first collection is an array called points , where each element is a coordinate pair [x, y] . Each pair represents a point on the plane. Multiple points are allowed to have the exact same coordinates, so duplicates must be counted separately. The...

Practice › Codeforces Solutions ›

Codeforces Round 110 (Div. 2)

Codeforces Round 110 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 800-1000 | Time: 4m 38s Problem Name Rating Tags Solve Time Verified A Game Outcome 800 brute-force 2m 19s ✓ B Trace 1000 geometry, sortings 2m 19s ✓

Practice › LeetCode › LeetCode 26xx ›

LeetCode 2613 - Beautiful Pairs

LeetCode Problem 2613 Difficulty: 🔴 Hard Topics: Array, Math, Divide and Conquer, Geometry, Sorting, Ordered Set Solution Problem Understanding The problem asks us to find a beautiful pair of indices (i, j) in two integer arrays nums1 and nums2 of equal length. A pair (i, j) is beautiful if it minimizes the sum of the absolute differences between the corresponding elements: |nums1[i] - nums1[j]| + |nums2[i] - nums2[j]| among all...

Practice › Codeforces Solutions ›

Codeforces Round 117 (Div. 2)

Codeforces Round 117 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1000-2200 | Time: 11m 48s Problem Name Rating Tags Solve Time Verified A Battlefield 2200 geometry, graphs, implementation 3m 47s ✓ B Vasya's Calendar 1000 implementation 3m 18s ✗ C Optimal Sum 2000 data-structures, greedy 1m 50s ✓ D Common Divisors 1400 brute-force, hashing, implementation 1m 36s ✓ E Wooden Fence 1800 dp...

Practice › Codeforces Solutions ›

Codeforces Round 250 (Div. 2)

Codeforces Round 250 (Div. 2) Type: Div. 2 | Problems: 1 | Verified: 1/1 | Rating range: 2500-2500 | Time: 1m 18s Problem Name Rating Tags Solve Time Verified E The Child and Polygon 2500 dp, geometry 1m 18s ✓

Practice › Codeforces Solutions › Codeforces Round 138 (Div. 1) ›

CF 223D - Spider

CF 223D - Spider Rating: 3000 Tags: geometry, graphs Solve time: 3m 42s Verified: no Solution Problem Understanding We are given a simple polygon whose vertices are listed in counterclockwise order. A spider starts at vertex s and wants to reach vertex t . The spider has two kinds of movement. The first move is walking along the polygon boundary. It may travel clockwise or counterclockwise, and the cost is...

Practice › Codeforces Solutions ›

Codeforces Round 199 (Div. 2)

Codeforces Round 199 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 2/3 | Rating range: 1200-2400 | Time: 16m 31s Problem Name Rating Tags Solve Time Verified A Xenia and Divisors 1200 greedy, implementation 6m 2s ✗ C Cupboard and Balloons 1900 geometry 5m 17s ✓ E Xenia and Tree 2400 data-structures, divide-and-conquer, trees 5m 12s ✓

Practice › Codeforces Solutions › Bayan 2012-2013 Elimination Round (ACM ICPC Rules, English statements) ›

CF 241C - Mirror Box

CF 241C - Mirror Box Rating: 2000 Tags: geometry, implementation Solve time: 1m 27s Verified: no Solution Problem Understanding The system describes a rectangular box where a laser beam enters through one small hole on the left wall and must exit through another hole on the right wall. Inside the box, there are horizontal mirror segments placed either on the floor or on the ceiling. Each mirror covers a segment...

Practice › Codeforces Solutions ›

Codeforces Round 140 (Div. 2)

Codeforces Round 140 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 1100-1300 | Time: 6m 2s Problem Name Rating Tags Solve Time Verified A Where do I Turn? 1300 geometry 2m 35s ✓ B Effective Approach 1100 implementation 3m 27s ✓

Practice › Codeforces Solutions ›

Codeforces Round 125 (Div. 2)

Codeforces Round 125 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 1/2 | Rating range: 900-1900 | Time: 3m 12s Problem Name Rating Tags Solve Time Verified A Hexadecimal's theorem 900 brute-force, constructive-algorithms, implementation 1m 37s ✓ B Special Olympics 1900 geometry 1m 35s ✗

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3027 - Find the Number of Ways to Place People II

LeetCode Problem 3027 Difficulty: 🔴 Hard Topics: Array, Math, Geometry, Sorting, Enumeration Solution Problem Understanding The problem asks us to determine how many valid placements of Alice and Bob exist on a 2D grid of points such that Alice can build a rectangular fence with her position as the upper left corner and Bob’s position as the lower right corner . A placement is only valid if no other person...

Practice › Codeforces Solutions › Codeforces Round 189 (Div. 1) ›

CF 319C - Kalila and Dimna in the Logging Industry

CF 319C - Kalila and Dimna in the Logging Industry Rating: 2100 Tags: dp, geometry Solve time: 2m 47s Verified: no Solution Problem Understanding We have a sequence of trees, each with a strictly increasing height, and each tree has an associated cost that represents the price of recharging the chainsaw after completely cutting the highest-indexed tree so far. Kalila and Dimna need to reduce all tree heights to zero....

Practice › Codeforces Solutions ›

Codeforces Round 138 (Div. 2)

Codeforces Round 138 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 1100-1500 | Time: 2m 3s Problem Name Rating Tags Solve Time Verified A Parallelepiped 1100 brute-force, geometry, math 1m 1s ✓ B Array 1500 bitmasks, implementation, two-pointers 1m 2s ✓

Practice › Codeforces Solutions › Codeforces Round 140 (Div. 2) ›

CF 227A - Where do I Turn?

CF 227A - Where do I Turn? Rating: 1300 Tags: geometry Solve time: 2m 35s Verified: yes Solution Problem Understanding The hero starts at point A , rides to point B , and then must continue toward point C . At point B , he is facing in the direction from A to B . We need to determine whether reaching C requires turning left, turning right, or continuing straight....

Practice › LeetCode › LeetCode 19xx ›

LeetCode 1956 - Minimum Time For K Virus Variants to Spread

LeetCode Problem 1956 Difficulty: 🔴 Hard Topics: Array, Math, Binary Search, Geometry, Enumeration Solution Problem Understanding The problem describes multiple virus variants spreading across an infinite 2D grid. Each virus starts from its own origin point on day 0 . Every day, a virus spreads one step in the four cardinal directions, which means after d days, a virus can reach every point whose Manhattan distance from its origin is...

Practice › Codeforces Solutions › Codeforces Round 245 (Div. 1) ›

CF 429D - Tricky Function

CF 429D - Tricky Function Rating: 2200 Tags: data structures, divide and conquer, geometry Solve time: 1m 9s Verified: yes Solution Problem Understanding We are given an array of integers a with n elements. The task is to select two distinct indices i and j and compute a function f(i, j) that combines both the squared distance between the indices and the squared sum of the elements strictly between them....

Practice › Codeforces Solutions ›

Codeforces Round 171 (Div. 2)

Codeforces Round 171 (Div. 2) Type: Div. 2 | Problems: 1 | Verified: 1/1 | Rating range: 1400-1400 | Time: 1m 28s Problem Name Rating Tags Solve Time Verified A Point on Spiral 1400 brute-force, geometry, implementation 1m 28s ✓

Practice › Codeforces Solutions › Codeforces Round 136 (Div. 1) ›

CF 220D - Little Elephant and Triangle

CF 220D - Little Elephant and Triangle Rating: 2500 Tags: geometry, math Solve time: 2m 25s Verified: no Solution Problem Understanding We work on the integer lattice inside a rectangle. Every point $(x,y)$ with $0 \le x \le w$ and $0 \le y \le h$ is available. We must count ordered triples of distinct lattice points that form a nondegenerate triangle whose area is an integer. The word "ordered" changes...

Practice › LeetCode › LeetCode 33xx ›

LeetCode 3382 - Maximum Area Rectangle With Point Constraints II

LeetCode Problem 3382 Difficulty: 🔴 Hard Topics: Array, Math, Binary Indexed Tree, Segment Tree, Geometry, Sorting Solution Problem Understanding The problem asks us to find the maximum area rectangle that can be formed from a given set of points on a 2D plane, under strict constraints. Each rectangle must have its edges parallel to the x and y axes, must use exactly four points from the input as corners, and...

Practice › Codeforces Solutions › Codeforces Round 117 (Div. 2) ›

CF 182A - Battlefield

CF 182A - Battlefield Rating: 2200 Tags: geometry, graphs, implementation, shortest paths Solve time: 3m 47s Verified: yes Solution Problem Understanding We are asked to simulate movement across a 2D plane from a starting point $A$ to a destination $B$ while avoiding a periodic laser. The laser alternates between charging and firing, with durations $a$ and $b$ seconds, respectively. During the firing phase, Vasya must be inside a trench to...

Practice › Codeforces Solutions › Testing Round 6 ›

CF 306D - Polygon

CF 306D - Polygon Rating: 2300 Tags: constructive algorithms, geometry Solve time: 2m 9s Verified: no Solution Problem Understanding We need to construct a convex polygon with exactly n vertices such that every interior angle is equal, but every side length is different. A polygon where all angles are equal is called equiangular. For a convex equiangular polygon, the direction of each edge is fixed. If we walk around the...

Practice › Codeforces Solutions ›

Codeforces Round 253 (Div. 1)

Codeforces Round 253 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 1/2 | Rating range: 1800-3100 | Time: 3m 6s Problem Name Rating Tags Solve Time Verified B Andrey and Problem 1800 greedy, math, probabilities 1m 14s ✓ E Gena and Second Distance 3100 geometry 1m 52s ✗

Practice › LeetCode › LeetCode 24xx ›

LeetCode 2481 - Minimum Cuts to Divide a Circle

LeetCode Problem 2481 Difficulty: 🟢 Easy Topics: Math, Geometry Solution Problem Understanding The problem asks for the minimum number of straight cuts required to divide a circle into n equal slices . A valid cut can either pass through the center and touch two points on the circle, or touch one point on the circle and pass through the center. The input is a single integer n representing the desired...

Practice › Codeforces Solutions ›

Codeforces Round 128 (Div. 2)

Codeforces Round 128 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1200-2300 | Time: 6m 39s Problem Name Rating Tags Solve Time Verified A Two Problems 1200 brute-force, implementation 1m 6s ✓ B Game on Paper 1300 brute-force, implementation 1m 41s ✓ C Photographer 1400 greedy, sortings 1m 5s ✓ D Hit Ball 1700 geometry, implementation, math 1m 20s ✗ E Transportation 2300 greedy,...

Practice › LeetCode › LeetCode 22xx ›

LeetCode 2280 - Minimum Lines to Represent a Line Chart

LeetCode Problem 2280 Difficulty: 🟡 Medium Topics: Array, Math, Geometry, Sorting, Number Theory Solution Problem Understanding In this problem, we are given a list of stock prices over different days. Each element in stockPrices is a pair: [day, price] This represents a point on a 2D graph where: The X-axis is the day The Y-axis is the stock price on that day The line chart is formed by connecting consecutive...

Practice › Codeforces Solutions › Codeforces Round 165 (Div. 2) ›

CF 270A - Fancy Fence

CF 270A - Fancy Fence Rating: 1100 Tags: geometry, implementation, math Solve time: 1m 12s Verified: yes Solution Problem Understanding We are asked to determine whether a robot, which can only make fence corners at a fixed angle a , can construct a regular polygon. A regular polygon is defined as a closed shape with all sides and all angles equal. The input consists of several test cases, each giving...

Practice › Codeforces Solutions ›

Codeforces Round 113 (Div. 2)

Codeforces Round 113 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 1100-2500 | Time: 11m 49s Problem Name Rating Tags Solve Time Verified A Rank List 1100 binary-search, implementation, sortings 1m 31s ✓ B Polygons 2100 geometry, sortings 3m 7s ✓ C Median 1500 greedy, math, sortings 1m 37s ✓ D Shoe Store 2500 dp, graph-matchings, greedy 2m 34s ✓ E Tetrahedron 1500 dp,...

Practice › Codeforces Solutions › Codeforces Round 152 (Div. 2) ›

CF 248C - Robo-Footballer

CF 248C - Robo-Footballer Rating: 2000 Tags: binary search, geometry Solve time: 2m Verified: no Solution Problem Understanding We are working inside a rectangular football field where the left side contains a goal segment on the vertical line $x = 0$, and the right side contains a horizontal wall at height $y = y_w$. A ball starts at a given point $(x_b, y_b)$ and must be kicked as a straight...

Practice › Codeforces Solutions ›

Codeforces Round 101 (Div. 2)

Codeforces Round 101 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 800-2300 | Time: 10m 27s Problem Name Rating Tags Solve Time Verified A Amusing Joke 800 implementation, sortings, strings 1m 31s ✓ B Hopscotch 1400 geometry, math 1m 26s ✓ C Queue 1800 constructive-algorithms, greedy, sortings 2m 24s ✗ D Take-off Ramps 2300 graphs, shortest-paths 2m 15s ✓ E Clearing Up 2300 constructive-algorithms,...

Practice › Codeforces Solutions › Codeforces Round 199 (Div. 2) ›

CF 342C - Cupboard and Balloons

CF 342C - Cupboard and Balloons Rating: 1900 Tags: geometry Solve time: 5m 17s Verified: yes Solution Problem Understanding Xenia has a cupboard shaped like a semicircular arch on top of two vertical walls. The semicircle has radius r and the walls have height h , with the cupboard’s depth also equal to r . Inside, she wants to store spherical balloons of radius 1. We are asked to calculate...

Practice › LeetCode › LeetCode 21xx ›

LeetCode 2152 - Minimum Number of Lines to Cover Points

LeetCode Problem 2152 Difficulty: 🟡 Medium Topics: Array, Hash Table, Math, Dynamic Programming, Backtracking, Bit Manipulation, Geometry, Bitmask Solution Problem Understanding This problem asks us to determine the minimum number of straight lines needed to cover a given set of points on an X-Y plane. Each point is defined by its (x, y) coordinates, and a straight line can pass through any number of points as long as they are...

Practice › Codeforces Solutions › Codeforces Round 123 (Div. 2) ›

CF 195D - Analyzing Polyline

CF 195D - Analyzing Polyline Rating: 1900 Tags: geometry, math, sortings Solve time: 1m 28s Verified: no Solution Problem Understanding We are asked to consider a set of linear functions, each defined by a slope $k_i$ and intercept $b_i$, and to analyze their sum. If we take the sum of $n$ such functions, the resulting graph is piecewise-linear, meaning it is composed of straight line segments joined at certain x-coordinates....

Practice › Codeforces Solutions › Codeforces Round 150 (Div. 1) ›

CF 243D - Cubes

CF 243D - Cubes Rating: 2700 Tags: data structures, dp, geometry, two pointers Solve time: 3m 9s Verified: yes Solution Problem Understanding We are given an n × n grid representing a city built from unit cubes stacked in towers. Each cell of the grid contains an integer indicating the height of the tower at that location. Petya observes the city from a very far distance in the horizontal plane...

Practice › Codeforces Solutions › Codeforces Round 253 (Div. 1) ›

CF 442E - Gena and Second Distance

CF 442E - Gena and Second Distance Rating: 3100 Tags: geometry Solve time: 1m 52s Verified: no Solution Problem Understanding We are asked to maximize a geometric metric called "beauty" within a rectangle. The rectangle is axis-aligned and has width w and height h . Inside it, there are n given points with coordinates (x_i, y_i) . For any candidate point (X, Y) inside the rectangle, we compute its Euclidean...

Practice › Codeforces Solutions › Codeforces Round 152 (Div. 1) ›

CF 249D - Donkey and Stars

CF 249D - Donkey and Stars Rating: 2700 Tags: data structures, dp, geometry, math, sortings Solve time: 1m 56s Verified: no Solution Problem Understanding We are asked to find the longest chain of stars the Donkey can select under a geometric rule. The stars are points on a plane, and we begin at the origin. From any star, we imagine two rays at fixed angles relative to the horizontal axis....

Practice › Codeforces Solutions › Croc Champ 2013 - Round 2 ›

CF 293D - Ksusha and Square

CF 293D - Ksusha and Square Rating: 2700 Tags: geometry, math, probabilities, two pointers Solve time: 1m 59s Verified: yes Solution Problem Understanding We are given a convex polygon with integer coordinates. Inside this polygon, including its boundary, there are finitely many lattice points. We choose two distinct lattice points uniformly at random, then construct a square whose diagonal is the segment between those two points. The task is to...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3009 - Maximum Number of Intersections on the Chart

LeetCode Problem 3009 Difficulty: 🔴 Hard Topics: Array, Hash Table, Math, Binary Indexed Tree, Geometry, Sweep Line, Sorting Solution I can provide the full guide, but I want to avoid giving you a technically incorrect reference document. For LeetCode 3009 , there are two subtly different interpretations that materially change the optimal algorithm and correctness proof: whether intersections at a chart vertex (k, y[k]) count once or twice when both...

Practice › Codeforces Solutions › Codeforces Round 100 ›

CF 140F - New Year Snowflake

CF 140F - New Year Snowflake Rating: 2600 Tags: geometry, sortings Solve time: 1m 51s Verified: yes Solution Problem Understanding We are given a set of points on the plane representing the crystals that survived after part of a symmetric snowflake melted. Originally, the full set of crystals had central symmetry: there existed some point $C$ such that for every crystal $P$, the point reflected through $C$, namely $2C -...

Practice › Codeforces Solutions › Codeforces Round 250 (Div. 2) ›

CF 437E - The Child and Polygon

CF 437E - The Child and Polygon Rating: 2500 Tags: dp, geometry Solve time: 1m 18s Verified: yes Solution Problem Understanding We are asked to count how many ways a simple polygon with $n$ vertices can be triangulated. Triangulation here means splitting the polygon into triangles that exactly cover the polygon without overlap and without introducing new points. Each triangle must have vertices only from the polygon's vertices, and every...

Practice › Codeforces Solutions › Codeforces Round 124 (Div. 1) ›

CF 196C - Paint Tree

CF 196C - Paint Tree Rating: 2200 Tags: constructive algorithms, divide and conquer, geometry, sortings, trees Solve time: 1m 40s Verified: no Solution Problem Understanding We are asked to embed a tree onto a set of points on a plane in such a way that tree edges correspond to straight line segments connecting the points. Each vertex of the tree must be mapped to a distinct point, and for any...

Practice › Codeforces Solutions › Croc Champ 2012 - Round 2 (Unofficial Div. 2 Edition) ›

CF 181A - Series of Crimes

CF 181A - Series of Crimes Rating: 800 Tags: brute force, geometry, implementation Solve time: 2m 48s Verified: yes Solution Problem Understanding We are given a map of a city as an n × m grid, where each cell represents a district. Three of the districts have been robbed, marked by * , and all other districts are empty ( . ). The task is to determine the location of...

Practice › Codeforces Solutions ›

Coder-Strike 2014 - Finals (online edition, Div. 1)

Coder-Strike 2014 - Finals (online edition, Div. 1) Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1000-2600 | Time: 8m 34s Problem Name Rating Tags Solve Time Verified A Start Up 1000 implementation 1m 24s ✓ B Online Meeting 1800 implementation 2m 4s ✗ C Bug in Code 1900 data-structures, graphs, implementation 1m 57s ✓ D Cup Trick 2200 data-structures 1m 9s ✓ E Playing the...

Practice › Codeforces Solutions ›

Croc Champ 2013 - Round 2

Croc Champ 2013 - Round 2 Type: Special | Problems: 4 | Verified: 4/4 | Rating range: 1500-2700 | Time: 8m 33s Problem Name Rating Tags Solve Time Verified A Weird Game 1500 games, greedy 53s ✓ C Cube Problem 2400 brute-force, math, number-theory 1m 36s ✓ D Ksusha and Square 2700 geometry, math, probabilities 1m 59s ✓ E Close Vertices 2700 data-structures, divide-and-conquer, trees 4m 5s ✓

Practice › Codeforces Solutions ›

Codeforces Round 238 (Div. 1)

Codeforces Round 238 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 0/2 | Rating range: 2200-2800 | Time: 6m 36s Problem Name Rating Tags Solve Time Verified D Hill Climbing 2200 dfs-and-similar, geometry, trees 2m 13s ✗ E Hamming Triples 2800 implementation, math, two-pointers 4m 23s ✗

Practice › LeetCode › LeetCode 32xx ›

LeetCode 3235 - Check if the Rectangle Corner Is Reachable

LeetCode Problem 3235 Difficulty: 🔴 Hard Topics: Array, Math, Depth-First Search, Breadth-First Search, Union-Find, Geometry Solution Problem Understanding The problem asks whether there is a clear, unobstructed path from the bottom-left corner (0, 0) to the top-right corner (xCorner, yCorner) of a rectangle, such that the path does not touch or go inside any given circles. Each circle is represented by its center (xi, yi) and radius ri . The...

Practice › Codeforces Solutions ›

April Fools Day Contest 2014

April Fools Day Contest 2014 Type: April Fools | Problems: 6 | Verified: 0/6 | Rating range: 1500-2200 | Time: 15m 44s Problem Name Rating Tags Solve Time Verified A The Great Game 1700 *special 4m 22s ✗ B Mysterious Language 1700 *special 57s ✗ D Big Data 1700 *special 1m 2s ✗ F 000001 1900 *special 6m 57s ✗ G On a plane 2200 *special, geometry 1m 53s ✗...

Practice › Codeforces Solutions › Codeforces Round 159 (Div. 2) ›

CF 257C - View Angle

CF 257C - View Angle Rating: 1800 Tags: brute force, geometry, math Solve time: 2m 43s Verified: yes Solution Problem Understanding We are asked to find the smallest angle with its vertex at the origin that contains all given points (mannequins) on a 2D plane. Each point is defined by integer coordinates, and no mannequin is located at the origin itself. The goal is to compute this angle in degrees...

Practice › Codeforces Solutions ›

Codeforces Round 187 (Div. 1)

Codeforces Round 187 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 2/3 | Rating range: 2000-2900 | Time: 6m 22s Problem Name Rating Tags Solve Time Verified B Sereja and Periods 2000 binary-search, dfs-and-similar, strings 1m 23s ✓ D Sereja and Straight Lines 2500 binary-search, data-structures, geometry 1m 45s ✓ E Sereja and Squares 2900 dp 3m 14s ✗

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3047 - Find the Largest Area of Square Inside Two Rectangles

LeetCode Problem 3047 Difficulty: 🟡 Medium Topics: Array, Math, Geometry Solution Problem Understanding The problem asks us to find the largest square that can fit inside the overlapping region of at least two rectangles on a 2D plane. Each rectangle is axis-aligned, meaning its sides are parallel to the x-axis and y-axis. The rectangles are defined by their bottom-left and top-right coordinates, which are given as integer pairs in two...

Practice › Codeforces Solutions › Codeforces Beta Round 69 (Div. 1 Only) ›

CF 77E - Martian Food

CF 77E - Martian Food Rating: 2800 Tags: geometry Solve time: 2m 22s Verified: no Solution Problem Understanding We have a large circle, the plate, with radius R . Inside it there is another circle, the Golden Honduras, with radius r . The Honduras circle is tangent to the plate from the inside, so its center is exactly R - r units away from the plate center. After that, smaller...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 963 - Minimum Area Rectangle II

LeetCode Problem 963 Difficulty: 🟡 Medium Topics: Array, Hash Table, Math, Geometry Solution Problem Understanding The problem gives us a collection of unique points on a 2D plane. Our task is to determine the minimum possible area of any rectangle that can be formed using exactly four of these points as vertices. The important detail is that the rectangle does not need to be aligned with the coordinate axes. This...

Practice › Codeforces Solutions › School Personal Contest #2 (Winter Computer School 2010/11) - Codeforces Beta Round 43 (ACM-ICPC Rules) ›

CF 46G - Emperor's Problem

CF 46G - Emperor's Problem Rating: 2500 Tags: geometry Solve time: 1m 33s Verified: no Solution Problem Understanding We are asked to construct a convex polygon with $n$ vertices that satisfies three conditions. First, all vertices must lie on lattice points, meaning each coordinate is an integer. Second, all sides must have distinct lengths. Third, among all polygons that satisfy these two conditions, the one with the minimal possible longest...

Practice › LeetCode › LeetCode 12xx ›

LeetCode 1232 - Check If It Is a Straight Line

LeetCode Problem 1232 Difficulty: 🟢 Easy Topics: Array, Math, Geometry Solution Problem Understanding The problem asks us to determine whether a given set of points in a 2D Cartesian plane all lie on a single straight line. The input is a list of integer coordinates, where each coordinate [x, y] represents a point. The expected output is a boolean: true if all the points lie on a straight line, and...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 973 - K Closest Points to Origin

LeetCode Problem 973 Difficulty: 🟡 Medium Topics: Array, Math, Divide and Conquer, Geometry, Sorting, Heap (Priority Queue), Quickselect Solution Problem Understanding This problem asks us to find the k points that are closest to the origin (0,0) from a list of 2D points. Each point is given as a pair [x, y] , and the distance is defined using the Euclidean formula, sqrt(x^2 + y^2) . The input consists of...

Practice › Codeforces Solutions › Manthan 2011 ›

CF 67E - Save the City!

CF 67E - Save the City! Rating: 2500 Tags: geometry Solve time: 2m 4s Verified: yes Solution Problem Understanding We are given a simple polygon listed in clockwise order. The first two vertices form a horizontal edge AB , and every other vertex lies strictly on the same side of that edge. Along the segment AB , every integer-coordinate point is a possible location for a watchtower. For a watchtower...

Practice › Codeforces Solutions › Yandex.Algorithm 2011: Qualification 2 ›

CF 82E - Corridor

CF 82E - Corridor Rating: 2600 Tags: geometry Solve time: 2m 6s Verified: yes Solution Problem Understanding We are asked to calculate the area of the floor in a house that is illuminated by two light sources placed symmetrically outside a horizontal strip representing the house. The house extends infinitely in the horizontal direction, but vertically it is bounded by the lines $y = h$ and $y = -h$. Windows...

Practice › Codeforces Solutions › Codeforces Beta Round 90 ›

CF 119E - Alternative Reality

CF 119E - Alternative Reality Rating: 2400 Tags: geometry Solve time: 1m 30s Verified: yes Solution Problem Understanding We are given a three-dimensional space containing $n$ fixed points, representing the centers of energy spheres. There are $m$ levels, and in each level the player starts at a plane passing through the origin. The player can construct spheres of any radius $R$ at the given centers, paying a cost equal to...

Practice › Codeforces Solutions › Codeforces Beta Round 66 ›

CF 73F - Plane of Tanks

CF 73F - Plane of Tanks Rating: 2900 Tags: brute force, geometry Solve time: 3m 6s Verified: yes Solution Problem Understanding We have a tank that wants to move from point A to point B along the straight segment connecting them. The tank moves with constant speed $v$, which we must choose as small as possible. There are $n$ enemy tanks placed on the plane. Each enemy turret initially points...

Practice › Codeforces Solutions ›

Codeforces Beta Round 30 (Codeforces format)

Codeforces Beta Round 30 (Codeforces format) Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1400-2800 | Time: 7m 26s Problem Name Rating Tags Solve Time Verified A Accounting 1400 brute-force, math 1m 23s ✓ B Codeforces World Finals 1700 implementation 1m 1s ✓ C Shooting Gallery 1800 dp, probabilities 1m ✓ D King's Problem? 2600 geometry, greedy 2m 12s ✗ E Tricky and Clever Password 2800 binary-search,...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 223 - Rectangle Area

LeetCode Problem 223 Difficulty: 🟡 Medium Topics: Math, Geometry Solution Problem Understanding The problem gives the coordinates of two axis-aligned rectangles on a 2D plane. Each rectangle is represented using two corner points: Bottom-left corner (x1, y1) Top-right corner (x2, y2) For the first rectangle, the coordinates are: (ax1, ay1) for the bottom-left (ax2, ay2) for the top-right For the second rectangle, the coordinates are: (bx1, by1) for the bottom-left...

Practice › Codeforces Solutions › Codeforces Beta Round 33 (Codeforces format) ›

CF 33D - Knights

CF 33D - Knights Rating: 2000 Tags: geometry, graphs, shortest paths, sortings Solve time: 1m 32s Verified: yes Solution Problem Understanding We are given a map of Berland with several control points and circular fences. Each knight occupies a control point. Fences separate the kingdom into regions, and a knight must cross fences to move between control points. For multiple queries, we need to determine the minimum number of fences...

Practice › Codeforces Solutions › Codeforces Beta Round 14 (Div. 2) ›

CF 14C - Four Segments

CF 14C - Four Segments Rating: 1700 Tags: brute force, constructive algorithms, geometry, implementation, math Solve time: 1m 48s Verified: yes Solution Problem Understanding We are given exactly four line segments on the 2D plane. Every segment is axis-aligned, or may even degenerate into a single point. The task is to decide whether these four segments together form the border of one rectangle with positive area, where all rectangle sides...

Practice › Codeforces Solutions ›

Codeforces Beta Round 2

Codeforces Beta Round 2 Type: Beta | Problems: 3 | Verified: 2/3 | Rating range: 1500-2600 | Time: 5m 52s Problem Name Rating Tags Solve Time Verified A Winner 1500 hashing, implementation 1m 9s ✓ B The least round way 2000 dp, math 3m 7s ✗ C Commentator problem 2600 geometry 1m 36s ✓

Practice › LeetCode › LeetCode 05xx ›

LeetCode 593 - Valid Square

LeetCode Problem 593 Difficulty: 🟡 Medium Topics: Math, Geometry Solution Problem Understanding The problem gives four points in a 2D coordinate system and asks whether those four points form a valid square. The points are not provided in any guaranteed order, which means we cannot assume adjacent points or diagonally opposite points are already grouped correctly. A square must satisfy two geometric properties simultaneously. First, all four sides must have...

Practice › Codeforces Solutions › Codeforces Beta Round 69 (Div. 2 Only) ›

CF 80B - Depression

CF 80B - Depression Rating: 1200 Tags: geometry, math Solve time: 1m 38s Verified: yes Solution Problem Understanding We are given a digital time in HH:MM format and need to determine how far the analog clock hands must rotate from the initial position 12:00 . The clock starts with both hands pointing at 12. We may rotate each hand independently, and only in the clockwise direction. The task is to...

Practice › Codeforces Solutions ›

Codeforces Beta Round 60

Codeforces Beta Round 60 Type: Beta | Problems: 5 | Verified: 3/5 | Rating range: 1700-2900 | Time: 11m 31s Problem Name Rating Tags Solve Time Verified A Harry Potter and Three Spells 1800 implementation, math 2m 2s ✓ B Harry Potter and the History of Magic 1700 brute-force, greedy, implementation 2m 33s ✗ C Harry Potter and the Golden Snitch 2100 binary-search, geometry 2m 11s ✓ D Harry Potter...

Practice › LeetCode › LeetCode 14xx ›

LeetCode 1401 - Circle and Rectangle Overlapping

LeetCode Problem 1401 Difficulty: 🟡 Medium Topics: Math, Geometry Solution Problem Understanding The problem gives two geometric shapes: A circle, defined by: radius center coordinates (xCenter, yCenter) An axis-aligned rectangle, defined by: bottom-left corner (x1, y1) top-right corner (x2, y2) The goal is to determine whether the circle and rectangle overlap. Two shapes overlap if there exists at least one point that belongs to both shapes simultaneously. The rectangle is...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 149 - Max Points on a Line

LeetCode Problem 149 Difficulty: 🔴 Hard Topics: Array, Hash Table, Math, Geometry Solution Problem Understanding The problem gives us a list of points on a 2D coordinate plane. Each point is represented as [x, y] , where x and y are integer coordinates. Our task is to determine the maximum number of points that lie on the same straight line. In other words, among all possible lines that can be...

Practice › Codeforces Solutions › Codeforces Beta Round 58 ›

CF 62C - Inquisition

CF 62C - Inquisition Rating: 2300 Tags: geometry, implementation, sortings Solve time: 1m 32s Verified: yes Solution Problem Understanding We are given up to 100 triangles on the plane. Each triangle represents a black spot on a white square. Triangles may overlap, intersect, or even completely cover one another. The task is to compute the perimeter of the union of all black regions. The perimeter here is not the sum...

Practice › Codeforces Solutions › Codeforces Beta Round 51 ›

CF 55E - Very simple problem

CF 55E - Very simple problem Rating: 2500 Tags: geometry, two pointers Solve time: 1m 49s Verified: no Solution Problem Understanding We are given a convex polygon defined by a list of points in clockwise order. For each query point in the plane, we need to count how many triangles formed by the polygon’s vertices contain that point strictly inside. The point is guaranteed not to lie on any side...

Practice › Codeforces Solutions › Codeforces Beta Round 62 ›

CF 68E - Contact

CF 68E - Contact Rating: 2900 Tags: geometry Solve time: 2m 17s Verified: yes Solution Problem Understanding We are given exactly four triangles. Each triangle represents the shape of one spaceship. A landing platform is just a set of points in the plane, called columns. A ship can land if we can choose three columns that form a triangle congruent to the ship. Congruence here allows every rigid motion: translation,...

Practice › Codeforces Solutions ›

Codeforces Beta Round 78 (Div. 1 Only)

Codeforces Beta Round 78 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1700-2700 | Time: 10m 13s Problem Name Rating Tags Solve Time Verified A Help Victoria the Wise 1700 brute-force, implementation 2m 12s ✓ B Help King 2200 implementation, probabilities, trees 1m 17s ✓ C Help Greg the Dwarf 2500 geometry, ternary-search 2m 29s ✓ D Help Monks 2500 constructive-algorithms 1m 50s...

Practice › LeetCode › LeetCode 14xx ›

LeetCode 1453 - Maximum Number of Darts Inside of a Circular Dartboard

LeetCode Problem 1453 Difficulty: 🔴 Hard Topics: Array, Math, Geometry Solution Problem Understanding In this problem, we are given the coordinates of several darts thrown onto a 2D plane. Each dart is represented as a point (x, y) . We are also given a radius r , which represents the radius of a circular dartboard. The task is to place a circle of radius r somewhere on the plane so...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 478 - Generate Random Point in a Circle

LeetCode Problem 478 Difficulty: 🟡 Medium Topics: Math, Geometry, Rejection Sampling, Randomized Solution LeetCode 478 - Generate Random Point in a Circle Problem Understanding This problem asks us to generate random points uniformly inside a circle. The circle is defined by its radius and the coordinates of its center. Every call to randPoint() must return a point [x, y] such that the point lies either inside the circle or exactly...

Practice › Codeforces Solutions ›

Codeforces Beta Round 18 (Div. 2 Only)

Codeforces Beta Round 18 (Div. 2 Only) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 1200-2000 | Time: 7m 50s Problem Name Rating Tags Solve Time Verified A Triangle 1500 brute-force, geometry 1m 48s ✓ B Platforms 1700 brute-force, math 1m 13s ✓ C Stripe 1200 data-structures, implementation 1m 43s ✓ D Seller Bob 2000 brute-force, dp, greedy 1m 54s ✓ E Flag 2 2000 dp...

Practice › Codeforces Solutions ›

Codeforces Beta Round 93 (Div. 2 Only)

Codeforces Beta Round 93 (Div. 2 Only) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 900-1000 | Time: 3m 25s Problem Name Rating Tags Solve Time Verified A Wasted Time 900 geometry 1m 39s ✓ B Canvas Frames 1000 implementation 1m 46s ✓

Practice › Codeforces Solutions ›

Codeforces Beta Round 39

Codeforces Beta Round 39 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1300-2600 | Time: 7m 51s Problem Name Rating Tags Solve Time Verified A Find Color 1300 constructive-algorithms, geometry, implementation 1m 24s ✓ B Repaintings 1600 math 1m 44s ✓ C Berland Square 2300 implementation, math 1m 38s ✓ D Interesting Sequence 2600 math 1m 55s ✓ E Number Table 2500 combinatorics 1m 10s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 36 ›

CF 36C - Bowls

CF 36C - Bowls Rating: 2200 Tags: geometry, implementation Solve time: 2m 5s Verified: no Solution Problem Understanding Each bowl is a frustum, a cone with its tip cut off. A bowl is described by its height h , bottom radius r , and top radius R . The bowls are stacked in the given order, always sharing the same vertical axis. Every new bowl is lowered as much as...

Practice › Codeforces Solutions ›

Codeforces Beta Round 24

Codeforces Beta Round 24 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1400-2400 | Time: 11m 12s Problem Name Rating Tags Solve Time Verified A Ring road 1400 graphs 3m 36s ✓ B F1 Champions 1500 implementation 2m 19s ✓ C Sequence of points 1800 geometry, implementation, math 2m 35s ✓ D Broken robot 2400 dp, math, probabilities 1m 34s ✓ E Berland collider 2300 binary-search 1m...

Practice › Codeforces Solutions › Codeforces Beta Round 1 ›

CF 1C - Ancient Berland Circus

Problem Understanding We are given the coordinates of three vertices of some regular polygon. The polygon itself is unknown: we do not know how many sides it has, where its center is, or which vertices the three points correspond to. Among all regular polygons that could contain these three points as vertices, we must find the one with the smallest area. The key geometric fact is that every regular polygon...

Practice › Codeforces Solutions › Codeforces Beta Round 60 ›

CF 65C - Harry Potter and the Golden Snitch

CF 65C - Harry Potter and the Golden Snitch Rating: 2100 Tags: binary search, geometry Solve time: 2m 11s Verified: yes Solution Problem Understanding The snitch moves along a fixed polyline in 3D space. It starts at the first vertex and travels segment by segment at constant speed vs . Harry starts at another point and can move in any direction at constant speed vp , where vp >= vs...

Practice › Codeforces Solutions › Codeforces Beta Round 73 (Div. 1 Only) ›

CF 87E - Mogohu-Rea Idol

CF 87E - Mogohu-Rea Idol Rating: 2600 Tags: geometry Solve time: 3m 16s Verified: yes Solution Problem Understanding We have three convex polygons on the plane. From each polygon we must choose one point, and the average of these three chosen points must equal the position of the idol. If the chosen altar points are $A, B, C$, and the idol is at point $P$, the condition is $$\frac{A+B+C}{3}=P$$ which...

Practice › Codeforces Solutions ›

Codeforces Beta Round 36

Codeforces Beta Round 36 Type: Beta | Problems: 5 | Verified: 2/5 | Rating range: 1300-2600 | Time: 9m 36s Problem Name Rating Tags Solve Time Verified A Extra-terrestrial Intelligence 1300 implementation 1m 21s ✓ B Fractal 1600 implementation 1m 52s ✓ C Bowls 2200 geometry, implementation 2m 5s ✗ D New Game with a Chess Piece 2300 games 1m 43s ✗ E Two Paths 2600 constructive-algorithms, dsu, graphs 2m...

Practice › Codeforces Solutions › Codeforces Beta Round 28 (Codeforces format) ›

CF 28E - DravDe saves the world

CF 28E - DravDe saves the world Rating: 2800 Tags: geometry, math Solve time: 2m 19s Verified: no Solution Problem Understanding We are given a simple polygon on the plane, representing the incubator area. DravDe starts at point $A$, which is guaranteed to lie strictly outside the polygon. The airplane moves with constant 3D velocity $V=(x_v,y_v,z_v)$. Since the plane starts at ground level and $z_v>0$, its altitude after time $t_1$...

Practice › LeetCode › LeetCode 12xx ›

LeetCode 1266 - Minimum Time Visiting All Points

LeetCode Problem 1266 Difficulty: 🟢 Easy Topics: Array, Math, Geometry Solution LeetCode 1266 - Minimum Time Visiting All Points Problem Understanding The problem gives a sequence of points on a 2D coordinate plane. Each point is represented as [x, y] , where x and y are integer coordinates. Your task is to determine the minimum number of seconds required to visit every point in the exact order they appear in...

Practice › Codeforces Solutions › Codeforces Beta Round 78 (Div. 1 Only) ›

CF 98C - Help Greg the Dwarf

CF 98C - Help Greg the Dwarf Rating: 2500 Tags: geometry, ternary search Solve time: 2m 29s Verified: yes Solution Problem Understanding We have an L-shaped corridor with widths a and b on the two branches. A rectangular coffin of fixed length l must be moved through the corner. The coffin can slide and rotate freely in the plane, but it can never leave the floor, so every intermediate position...

Practice › Codeforces Solutions › Codeforces Beta Round 2 ›

CF 2C - Commentator problem

Problem Understanding We are given three circles on the plane. Each circle represents a stadium, with a center point and a radius. We need to find a point from which all three stadiums are seen under the same angle. For a circle with radius $r$ observed from a point $P$, the visible angle is the angle between the two tangent lines from $P$ to the circle. If the distance from...

Practice › LeetCode › LeetCode 10xx ›

LeetCode 1030 - Matrix Cells in Distance Order

LeetCode Problem 1030 Difficulty: 🟢 Easy Topics: Array, Math, Geometry, Sorting, Matrix Solution Problem Understanding This problem asks us to return every cell in a matrix, ordered by its Manhattan distance from a given center cell. We are given four integers: rows , the number of rows in the matrix cols , the number of columns in the matrix rCenter , the row index of the reference cell cCenter ,...

Practice › LeetCode › LeetCode 08xx ›

LeetCode 836 - Rectangle Overlap

LeetCode Problem 836 Difficulty: 🟢 Easy Topics: Math, Geometry Solution LeetCode 836, Rectangle Overlap Problem Understanding The problem gives us two axis-aligned rectangles , meaning their sides are parallel to the X-axis and Y-axis. Each rectangle is represented as: [x1, y1, x2, y2] Where: (x1, y1) is the bottom-left corner (x2, y2) is the top-right corner The task is to determine whether these two rectangles overlap with positive area ....

Practice › Codeforces Solutions › Codeforces Beta Round 82 (Div. 2) ›

CF 106E - Space Rescuers

CF 106E - Space Rescuers Rating: 2100 Tags: geometry, ternary search Solve time: 5m 23s Verified: no Solution Problem Understanding We are asked to place a space rescue station in three-dimensional space such that the maximum distance from it to any of the given planets is minimized. Each planet is represented by its coordinates $(x, y, z)$. The input consists of an integer $n$ representing the number of planets followed...

Practice › Codeforces Solutions › Codeforces Beta Round 9 (Div. 2 Only) ›

CF 9B - Running Student

CF 9B - Running Student Rating: 1200 Tags: brute force, geometry, implementation Solve time: 1m 26s Verified: yes Solution Problem Understanding The student is already riding a bus that moves along the x-axis from left to right. The bus stops at fixed positions (xi, 0) in increasing order. At any stop except the first one, the student may get off and run directly to the university located at (xu, yu)...

Practice › Codeforces Solutions › Codeforces Beta Round 50 ›

CF 54E - Vacuum Сleaner

CF 54E - Vacuum \u0421leaner Rating: 2700 Tags: geometry Solve time: 3m 46s Verified: yes Solution Problem Understanding We are given the top view of a robotic vacuum cleaner as a convex polygon. The room corner is the usual 90 degree corner formed by two perpendicular walls. We may rotate the vacuum cleaner by any angle and then push it as far as possible into the corner. The cleaner cannot...

Practice › Codeforces Solutions ›

Codeforces Beta Round 69 (Div. 2 Only)

Codeforces Beta Round 69 (Div. 2 Only) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 800-1200 | Time: 2m 56s Problem Name Rating Tags Solve Time Verified A Panoramix's Prediction 800 brute-force 1m 18s ✓ B Depression 1200 geometry, math 1m 38s ✓

Practice › Codeforces Solutions ›

School Team Contest 2 (Winter Computer School 2010/11)

School Team Contest 2 (Winter Computer School 2010/11) Type: Special | Problems: 10 | Verified: 6/10 | Rating range: 900-2700 | Time: 21m 26s Problem Name Rating Tags Solve Time Verified A Indian Summer 900 implementation 1m 23s ✓ B Cola 1500 implementation 1m 9s ✓ C Holidays 1300 implementation 1m 24s ✓ D Hyperdrive 1800 math 1m 5s ✓ E Anfisa the Monkey 1400 dp 2m 13s ✗ F...

Practice › Codeforces Solutions › Codeforces Beta Round 83 (Div. 1 Only) ›

CF 107E - Darts

CF 107E - Darts Rating: 2700 Tags: geometry, probabilities Solve time: 2m 19s Verified: yes Solution Problem Understanding We have several rectangles on the plane. Each rectangle represents a photo hanging on a wall. The rectangles may overlap, may share edges, may coincide completely, and may also be rotated arbitrarily. A dart is thrown uniformly at random over the entire wall, but we only care about throws that hit at...

Practice › LeetCode › LeetCode 15xx ›

LeetCode 1515 - Best Position for a Service Centre

LeetCode Problem 1515 Difficulty: 🔴 Hard Topics: Array, Math, Geometry, Randomized Solution Problem Understanding The problem asks us to find the optimal location for a service center on a 2D map such that the total Euclidean distance from the center to all customers is minimized. We are given the coordinates of customers as a list positions , where each element is a 2-element list [x, y] . The goal is...

Practice › Codeforces Solutions › Codeforces Beta Round 24 ›

CF 24C - Sequence of points

CF 24C - Sequence of points Rating: 1800 Tags: geometry, implementation, math Solve time: 2m 35s Verified: yes Solution Problem Understanding We are given a sequence of points on the 2D integer grid: a starting point M0 and a sequence of n points A0, A1, …, An-1, where n is always odd. We then define a new sequence M1, M2, … where each Mi is the reflection of Mi-1 over...

Practice › LeetCode › LeetCode 08xx ›

LeetCode 858 - Mirror Reflection

LeetCode Problem 858 Difficulty: 🟡 Medium Topics: Math, Geometry, Number Theory Solution LeetCode 858 - Mirror Reflection Problem Understanding This problem describes a square room with perfectly reflective walls. The room has side length p , and there are three receptors placed at three corners of the square: Receptor 0 is at the southeast corner Receptor 1 is at the northeast corner Receptor 2 is at the northwest corner The...

Practice › Codeforces Solutions › Codeforces Beta Round 97 (Div. 1) ›

CF 135B - Rectangle and Square

CF 135B - Rectangle and Square Rating: 1600 Tags: brute force, geometry, math Solve time: 2m 3s Verified: yes Solution Problem Understanding We are given eight distinct points on the plane. The task is to split them into two disjoint groups of four points each. One group must form a square. The other group must form a rectangle. A square is also allowed for the rectangle group, so the second...

Practice › Codeforces Solutions › Codeforces Beta Round 74 (Div. 1 Only) ›

CF 89D - Space mines

CF 89D - Space mines Rating: 2500 Tags: geometry Solve time: 4m 9s Verified: yes Solution Problem Understanding The Death Star is a sphere of radius R . Its center starts at point A and moves forever in a straight line with constant velocity vector v . Every mine consists of two kinds of geometry. The first part is a sphere centered at O with radius r . The second...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 335 - Self Crossing

LeetCode Problem 335 Difficulty: 🔴 Hard Topics: Array, Math, Geometry Solution Problem Understanding The problem describes a path traced on a two-dimensional grid. We begin at the origin (0, 0) and move according to the values in the distance array. The movement directions always rotate counter-clockwise in the following repeating order: north west south east Then the pattern repeats again. For example, if distance = [2,1,1,2] , the movement sequence...

Practice › LeetCode › LeetCode 08xx ›

LeetCode 812 - Largest Triangle Area

LeetCode Problem 812 Difficulty: 🟢 Easy Topics: Array, Math, Geometry Solution LeetCode 812, Largest Triangle Area Problem Understanding The problem gives us a list of unique points on a 2D X-Y plane. Each point is represented as a pair of integers [x, y] . Our task is to choose any three distinct points and compute the area of the triangle formed by those points. Among all possible triangles, we must...

Practice › Codeforces Solutions ›

Codeforces Beta Round 6 (Div. 2 Only)

Codeforces Beta Round 6 (Div. 2 Only) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 900-2600 | Time: 7m 21s Problem Name Rating Tags Solve Time Verified A Triangle 900 brute-force, geometry 1m 18s ✓ B President's Office 1100 implementation 1m 18s ✓ C Alice, Bob and Chocolate 1200 greedy, two-pointers 1m 29s ✓ D Lizards and Basements 2 2600 brute-force, dp 2m 18s ✓ E...

Practice › Codeforces Solutions › School Regional Team Contest, Saratov, 2011 ›

CF 120J - Minimum Sum

CF 120J - Minimum Sum Rating: 1900 Tags: divide and conquer, geometry, sortings Solve time: 2m 6s Verified: no Solution Problem Understanding We are given a set of points in two-dimensional space, where each point can be thought of as a vector from the origin. Each vector has two coordinates, x and y , and we are allowed to independently flip the sign of each coordinate. That is, for any...

Practice › Codeforces Solutions › Codeforces Beta Round 67 (Div. 2) ›

CF 75E - Ship's Shortest Path

CF 75E - Ship's Shortest Path Rating: 2400 Tags: geometry, shortest paths Solve time: 2m 29s Verified: yes Solution Problem Understanding We are given two points in the plane, the ship's starting position and destination, together with a convex polygon representing an island. Moving through the sea costs 1 per unit distance. Moving through the interior of the island costs 2 per unit distance. Moving along the polygon boundary is...

Practice › Codeforces Solutions › Codeforces Beta Round 32 (Div. 2, Codeforces format) ›

CF 32E - Hide-and-Seek

CF 32E - Hide-and-Seek Rating: 2400 Tags: geometry, implementation Solve time: 2m 25s Verified: yes Solution Problem Understanding We have two people represented as points on the plane, Victor and Peter. The room contains exactly two objects, a solid wall segment and a double-sided mirror segment. Victor wants to know whether he can see Peter either directly or through a single reflection in the mirror. A direct line of sight...

Practice › Codeforces Solutions › Codeforces Beta Round 47 ›

CF 50C - Happy Farm 5

CF 50C - Happy Farm 5 Rating: 2000 Tags: geometry Solve time: 55s Verified: yes Solution Problem Understanding We have a set of points on a 2D plane representing cows, each with integer coordinates. Vasya, the shepherd, must walk a closed path around all the cows in such a way that every cow lies strictly inside the path. The goal is to minimize the number of moves needed. Each move...

Practice › LeetCode › LeetCode 08xx ›

LeetCode 883 - Projection Area of 3D Shapes

LeetCode Problem 883 Difficulty: 🟢 Easy Topics: Array, Math, Geometry, Matrix Solution Problem Understanding The problem gives us an n x n matrix called grid . Each cell grid[i][j] represents how many 1 x 1 x 1 cubes are stacked vertically at position (i, j) on a flat surface. We must calculate the total area of the projections of this 3D structure onto three planes: The xy plane, which is...

Practice › Codeforces Solutions › Codeforces Beta Round 44 (Div. 2) ›

CF 47E - Cannon

CF 47E - Cannon Rating: 2200 Tags: data structures, geometry, sortings Solve time: 1m 54s Verified: no Solution Problem Understanding We have a scenario where a cannon at the origin shoots a number of balls with the same initial speed, each at a given angle. The goal is to determine where each ball lands after either hitting a vertical wall or reaching the ground. Each wall is a vertical segment...

Practice › Codeforces Solutions › Codeforces Beta Round 94 (Div. 1 Only) ›

CF 128E - Birthday

CF 128E - Birthday Rating: 2900 Tags: geometry, math Solve time: 1m 35s Verified: yes Solution Problem Understanding We are asked to determine the maximum number of banana pieces Maria can produce from a birthday cake decorated with n non-overlapping circular banana pieces using exactly k straight-line cuts. Each circle has a center coordinate (x, y) and a radius r . The goal is not to divide the cake evenly...

Practice › Codeforces Solutions › Unknown Language Round 3 ›

CF 100I - Rotation

CF 100I - Rotation Rating: 1500 Tags: *special, geometry, math Solve time: 4m 21s Verified: yes Solution Problem Understanding We are given a point $(x, y)$ on the 2D plane and an angle $k$ in degrees. The task is to rotate the point counter-clockwise around the origin by exactly $k$ degrees and print the coordinates of the new point. A rotation around the origin preserves the distance from the origin...

Practice › Codeforces Solutions › Codeforces Beta Round 13 ›

CF 13D - Triangles

CF 13D - Triangles Rating: 2600 Tags: dp, geometry Solve time: 1m 38s Verified: yes Solution Problem Understanding We have two sets of points on the plane. Red points may be used as triangle vertices, blue points are obstacles. No three points are collinear, which removes all degeneracies involving points on triangle borders. The task is to count how many triangles formed by red points contain no blue point strictly...

Practice › LeetCode › LeetCode 05xx ›

LeetCode 587 - Erect the Fence

LeetCode Problem 587 Difficulty: 🔴 Hard Topics: Array, Math, Geometry Solution Problem Understanding This problem is asking us to find the convex hull of a set of points on a 2D plane. The input trees is a list of coordinates where each coordinate [xi, yi] represents the location of a tree in the garden. Our goal is to enclose all trees with a fence using the minimum perimeter, which means...

Practice › Codeforces Solutions ›

Codeforces Beta Round 82 (Div. 2)

Codeforces Beta Round 82 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1000-2100 | Time: 13m 18s Problem Name Rating Tags Solve Time Verified A Card Game 1000 implementation 1m 37s ✓ B Choosing Laptop 1000 brute-force, implementation 2m 3s ✓ C Buns 1700 dp 1m 50s ✓ D Treasure Island 1700 brute-force, implementation 2m 25s ✓ E Space Rescuers 2100 geometry, ternary-search 5m...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 391 - Perfect Rectangle

LeetCode Problem 391 Difficulty: 🔴 Hard Topics: Array, Hash Table, Math, Geometry, Sweep Line Solution Problem Understanding This problem asks whether a collection of smaller axis-aligned rectangles perfectly forms one larger rectangle, with no gaps and no overlaps. Each rectangle is represented as: [xi, yi, ai, bi] where: (xi, yi) is the bottom-left corner (ai, bi) is the top-right corner Because the rectangles are axis-aligned, their sides are parallel to...

Practice › Codeforces Solutions › Codeforces Beta Round 6 (Div. 2 Only) ›

CF 6A - Triangle

CF 6A - Triangle Rating: 900 Tags: brute force, geometry Solve time: 1m 18s Verified: yes Solution Problem Understanding We are given four stick lengths, and we must choose exactly three of them. Depending on the relationship between those three lengths, there are three possible outcomes. If the chosen sticks can form a triangle with positive area, we print TRIANGLE . Geometrically, this means the sum of the two smaller...

Practice › LeetCode › LeetCode 16xx ›

LeetCode 1610 - Maximum Number of Visible Points

LeetCode Problem 1610 Difficulty: 🔴 Hard Topics: Array, Math, Geometry, Sliding Window, Sorting Solution Problem Understanding In this problem, we are standing at a fixed position on a 2D plane, represented by location = [posx, posy] . Around us, there are multiple points, each with integer coordinates. We are allowed to rotate in place, but we cannot move. Our vision works like a camera with a limited viewing angle. The...

Practice › Codeforces Solutions › Codeforces Beta Round 18 (Div. 2 Only) ›

CF 18A - Triangle

CF 18A - Triangle Rating: 1500 Tags: brute force, geometry Solve time: 1m 48s Verified: yes Solution Problem Understanding We are given three points on the plane with integer coordinates. These three points already form a valid triangle, meaning they are not collinear. The task is to classify the triangle into one of three categories. The triangle is RIGHT if one of its angles is exactly 90 degrees. The triangle...

Practice › Codeforces Solutions › Codeforces Beta Round 39 ›

CF 40A - Find Color

CF 40A - Find Color Rating: 1300 Tags: constructive algorithms, geometry, implementation, math Solve time: 1m 24s Verified: yes Solution Problem Understanding The plane is colored using concentric rings centered at the origin. Every ring between two consecutive integer distances alternates color. The borders themselves, meaning all points whose distance from the origin is an integer, are always black. For a point (x, y) , we need to determine whether...

Practice › LeetCode › LeetCode 10xx ›

LeetCode 1037 - Valid Boomerang

LeetCode Problem 1037 Difficulty: 🟢 Easy Topics: Array, Math, Geometry Solution Problem Understanding This problem asks us to determine whether three given points in a 2D Cartesian plane form a valid boomerang. A boomerang is defined as a set of three points that are all distinct and not in a straight line . In other words, the points must not coincide and must not be collinear. The input is always...

Practice › Codeforces Solutions ›

Codeforces Beta Round 9 (Div. 2 Only)

Codeforces Beta Round 9 (Div. 2 Only) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-2300 | Time: 8m 20s Problem Name Rating Tags Solve Time Verified A Die Roll 800 math, probabilities 2m 43s ✓ B Running Student 1200 brute-force, geometry, implementation 1m 26s ✓ C Hexadecimal's Numbers 1200 brute-force, implementation, math 1m 10s ✓ D How many trees? 1900 combinatorics, divide-and-conquer, dp 1m 13s...

Practice › Codeforces Solutions ›

Codeforces Beta Round 1

Codeforces Beta Round 1 Type: Beta | Problems: 3 | Verified: 3/3 | Rating range: 1000-2100 | Time: 10m 36s Problem Name Rating Tags Solve Time Verified A Theatre Square 1000 math 4m 1s ✓ B Spreadsheet 1600 implementation, math 4m 55s ✓ C Ancient Berland Circus 2100 geometry, math 1m 40s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 64 ›

CF 70D - Professor's task

CF 70D - Professor's task Rating: 2700 Tags: data structures, geometry Solve time: 2m 2s Verified: yes Solution Problem Understanding We are asked to maintain a set of points on a plane and support two operations: adding a point, and checking if a point lies inside the convex hull of the current set. The convex hull is the minimal convex polygon enclosing all points. Every point inside the polygon or...

Practice › Codeforces Solutions ›

Codeforces Beta Round 14 (Div. 2)

Codeforces Beta Round 14 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-1900 | Time: 7m 42s Problem Name Rating Tags Solve Time Verified A Letter 800 implementation 1m 8s ✓ B Young Photographer 1000 implementation 1m 20s ✓ C Four Segments 1700 brute-force, constructive-algorithms, geometry 1m 48s ✓ D Two Paths 1900 dfs-and-similar, dp, graphs 1m 27s ✓ E Camels 1900 dp 1m...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 939 - Minimum Area Rectangle

LeetCode Problem 939 Difficulty: 🟡 Medium Topics: Array, Hash Table, Math, Geometry, Sorting Solution Problem Understanding The problem gives us a collection of distinct points on a 2D plane. Each point is represented as [x, y] , where x is the horizontal coordinate and y is the vertical coordinate. Our task is to determine the minimum possible area of an axis-aligned rectangle that can be formed using four of these...

Practice › Codeforces Solutions ›

Codeforces Beta Round 47

Codeforces Beta Round 47 Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 800-2300 | Time: 6m 55s Problem Name Rating Tags Solve Time Verified A Domino piling 800 greedy, math 1m 5s ✓ B Choosing Symbol Pairs 1500 strings 1m 15s ✓ C Happy Farm 5 2000 geometry 55s ✓ D Bombing 2100 binary-search, dp, probabilities 1m 42s ✗ E Square Equation Roots 2300 math 1m 58s...

Practice › Codeforces Solutions › Codeforces Beta Round 23 ›

CF 23D - Tetragon

CF 23D - Tetragon Rating: 2600 Tags: geometry, math Solve time: 2m 11s Verified: no Solution Problem Understanding We are given three points in the plane. Each point is the midpoint of one side of an unknown strictly convex quadrilateral, and all four sides of that quadrilateral have equal length. The task is to reconstruct any valid quadrilateral that satisfies these conditions, or determine that no such quadrilateral exists. The...

Practice › Codeforces Solutions › Yandex.Algorithm 2011: Round 1 ›

CF 85E - Guard Towers

CF 85E - Guard Towers Rating: 2600 Tags: binary search, dsu, geometry, graphs, sortings Solve time: 3m 41s Verified: yes Solution Problem Understanding We have n towers on a 2D plane. Every tower must belong to exactly one of two generals. For each general, the cost he demands is the maximum Manhattan distance between any two towers assigned to him. The king only pays the larger of the two costs....

Practice › Codeforces Solutions › Codeforces Beta Round 70 (Div. 2) ›

CF 78D - Archer's Shot

CF 78D - Archer's Shot Rating: 2300 Tags: binary search, geometry, math, two pointers Solve time: 2m 7s Verified: yes Solution Problem Understanding We are asked to calculate how many hexagonal cells a single archer can fully cover with a circular attack of radius k , where the archer is positioned at the center of a cell. Each hexagon has side length 1. A cell counts as covered only if...

Practice › Codeforces Solutions › Codeforces Beta Round 93 (Div. 2 Only) ›

CF 127A - Wasted Time

CF 127A - Wasted Time Rating: 900 Tags: geometry Solve time: 1m 39s Verified: yes Solution Problem Understanding Scrooge signs papers by moving a pen along a polyline. The signature starts at the first point, then draws straight segments between consecutive points until the last point is reached. His pen speed is fixed at 50 millimeters per second, and he repeats the exact same signature k times. The task is...

Practice › Codeforces Solutions ›

Codeforces Beta Round 44 (Div. 2)

Codeforces Beta Round 44 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 800-2200 | Time: 8m 58s Problem Name Rating Tags Solve Time Verified A Triangular numbers 800 brute-force, math 1m 10s ✓ B Coins 1200 implementation 1m 42s ✓ C Crossword 2000 implementation 2m 32s ✗ D Safe 2200 brute-force 1m 40s ✓ E Cannon 2200 data-structures, geometry, sortings 1m 54s ✗

Practice › Codeforces Solutions › Codeforces Beta Round 75 (Div. 1 Only) ›

CF 91E - Igloo Skyscraper

CF 91E - Igloo Skyscraper Rating: 2500 Tags: data structures, geometry Solve time: 2m 44s Verified: yes Solution Problem Understanding Each walrus builds a skyscraper whose height changes linearly over time. Walrus i starts with height a[i] and gains b[i] floors every minute, so at time t its height equals: $$h_i(t) = a_i + b_i \cdot t$$ For every query [l, r, t] , we must find an index inside...

Practice › Codeforces Solutions ›

Codeforces Beta Round 58

Codeforces Beta Round 58 Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1300-2700 | Time: 8m 15s Problem Name Rating Tags Solve Time Verified A A Student's Dream 1300 greedy, math 1m 13s ✓ B Tyndex.Brome 1800 binary-search, implementation 1m 18s ✓ C Inquisition 2300 geometry, implementation, sortings 1m 32s ✓ D Wormhouse 2300 dfs-and-similar, graphs 2m 15s ✗ E World Evil 2700 dp, flows 1m 57s...

Practice › Codeforces Solutions ›

Codeforces Beta Round 97 (Div. 1)

Codeforces Beta Round 97 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1300-3000 | Time: 9m 14s Problem Name Rating Tags Solve Time Verified A Replacement 1300 greedy, implementation, sortings 1m 34s ✓ B Rectangle and Square 1600 brute-force, geometry, math 2m 3s ✓ C Zero-One 1900 constructive-algorithms, games, greedy 1m 50s ✓ D Cycle 2500 brute-force, dfs-and-similar, implementation 1m 50s ✓ E Weak...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 469 - Convex Polygon

LeetCode Problem 469 Difficulty: 🟡 Medium Topics: Array, Math, Geometry Solution Problem Understanding The problem gives us a sequence of points on a 2D plane. These points are connected in order, and the final point connects back to the first point, forming a polygon. Our task is to determine whether that polygon is convex. A polygon is convex if every internal angle is less than 180 degrees. Another equivalent geometric...

Practice › LeetCode › LeetCode 08xx ›

LeetCode 892 - Surface Area of 3D Shapes

LeetCode Problem 892 Difficulty: 🟢 Easy Topics: Array, Math, Geometry, Matrix Solution Problem Understanding The problem gives us an n x n matrix called grid , where each cell contains a non-negative integer. The value grid[i][j] represents how many 1 x 1 x 1 cubes are stacked vertically at position (i, j) . Each cube contributes surface area through its exposed faces. A single cube has 6 faces, but when...

Practice › Codeforces Solutions ›

Codeforces Beta Round 13

Codeforces Beta Round 13 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1000-2700 | Time: 7m 43s Problem Name Rating Tags Solve Time Verified A Numbers 1000 implementation, math 1m 3s ✓ B Letter A 2000 geometry, implementation 1m 45s ✓ C Sequence 2200 dp, sortings 1m 24s ✓ D Triangles 2600 dp, geometry 1m 38s ✓ E Holes 2700 data-structures, dsu 1m 53s ✓

Practice › Codeforces Solutions ›

Codeforces Beta Round 32 (Div. 2, Codeforces format)

Codeforces Beta Round 32 (Div. 2, Codeforces format) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-2400 | Time: 6m 58s Problem Name Rating Tags Solve Time Verified A Reconnaissance 800 brute-force 1m 5s ✓ B Borze 800 expression-parsing, implementation 1m 17s ✓ C Flea 1700 math 1m 12s ✓ D Constellation 1600 implementation 59s ✓ E Hide-and-Seek 2400 geometry, implementation 2m 25s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 30 (Codeforces format) ›

CF 30D - King's Problem?

CF 30D - King's Problem? Rating: 2600 Tags: geometry, greedy Solve time: 2m 12s Verified: no Solution Problem Understanding We have n + 1 cities. The first n cities lie on the x-axis at positions (x1, 0), (x2, 0), ..., (xn, 0) . One additional city is somewhere off the axis at (x_{n+1}, y_{n+1}) . The king starts from city k . He must visit every city at least once,...

Practice › Codeforces Solutions › Codeforces Beta Round 13 ›

CF 13B - Letter A

CF 13B - Letter A Rating: 2000 Tags: geometry, implementation Solve time: 1m 45s Verified: yes Solution Problem Understanding We are given three line segments on a 2D plane. We must decide whether these three segments can be interpreted as the shape of the capital letter A. The structure of the letter is very rigid. Two segments must meet at a common endpoint and form the two slanted legs of...

Practice › Codeforces Solutions › School Team Contest 2 (Winter Computer School 2010/11) ›

CF 44F - BerPaint

CF 44F - BerPaint Rating: 2700 Tags: geometry, graphs Solve time: 2m 57s Verified: no Solution Problem Understanding We have a rectangular canvas of size W × H . Initially the whole canvas is white. Then several black line segments are drawn on it. After that, a sequence of flood-fill operations is applied. A flood-fill chooses a point and a color. Every point connected to the chosen point through regions...

Practice › Codeforces Solutions ›

Codeforces Beta Round 33 (Codeforces format)

Codeforces Beta Round 33 (Codeforces format) Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1200-2600 | Time: 18m 29s Problem Name Rating Tags Solve Time Verified A What is for dinner? 1200 greedy, implementation 3m 53s ✓ B String Problem 1800 shortest-paths 7m 1s ✓ C Wonderful Randomized Sum 1800 greedy 3m 6s ✓ D Knights 2000 geometry, graphs, shortest-paths 1m 32s ✓ E Helper 2600 -...

Practice › Codeforces Solutions › Codeforces Beta Round 8 ›

CF 8D - Two Friends

CF 8D - Two Friends Rating: 2600 Tags: binary search, geometry Solve time: 1m 54s Verified: yes Solution Problem Understanding We have three points on a plane: the cinema, the house, and the shop. Bob starts at the cinema and eventually reaches the house. Alan also starts at the cinema and ends at the house, but his route must pass through the shop at some moment. Both people may walk...

Practice › LeetCode › LeetCode (archived) › LeetCode 10xx ›

LeetCode 1037: Valid Boomerang

Problem Restatement We are given three points in the 2D plane: points[0] , points[1] , points[2] . A boomerang is a set of three points that are all distinct and not collinear. Return true if the three points form a boomerang. The official constraints state that points.length == 3 and 0 <= points[i][j] <= 100 . Input and Output Item Meaning Input Three 2D points [[x1,y1],[x2,y2],[x3,y3]] Output true if points...

Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 963: Minimum Area Rectangle II

Problem Restatement We are given a list of unique points in the x-y plane. Each point is: [x, y] We need to find the minimum area of any rectangle formed by four of these points. The rectangle sides do not need to be parallel to the axes. A rotated rectangle is allowed. If no rectangle can be formed, return 0 . Answers within 10^-5 of the actual answer are accepted....

Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 892: Surface Area of 3D Shapes

Problem Restatement We are given an n x n grid. Each value: grid[i][j] represents a tower of grid[i][j] unit cubes placed on cell (i, j) . After placing the cubes, directly adjacent cubes are glued together. We need to return the total exposed surface area of the resulting 3D shape. The bottom face counts as part of the surface area. LeetCode defines each cube as 1 x 1 x 1...

Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 939: Minimum Area Rectangle

Problem Restatement We are given a list of unique points on a 2D plane. Each point is represented as: [x, y] We need to find the minimum area of a rectangle whose four corners are all in points . The rectangle must have sides parallel to the X-axis and Y-axis. So rotated rectangles do not count. If no such rectangle exists, return: 0 The official statement asks for the minimum...

Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 789: Escape The Ghosts

Problem Restatement We start at point: [0, 0] We want to reach: target = [target_x, target_y] There are several ghosts. Each ghost starts at: ghosts[i] = [ghost_x, ghost_y] Each turn, we and all ghosts may move one step north, south, east, or west. Everyone moves at the same speed. We escape only if we reach the target before any ghost can reach us. If we and a ghost arrive at...

Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 836: Rectangle Overlap

Problem Restatement We are given two axis-aligned rectangles, rec1 and rec2 . Each rectangle is represented as: [x1, y1, x2, y2] where: Coordinate Meaning (x1, y1) Bottom-left corner (x2, y2) Top-right corner We need to return True if the two rectangles overlap. Overlap means their intersection has positive area. If two rectangles only touch at an edge or corner, they do not overlap. Input and Output Item Meaning Input Two...

Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 711: Number of Distinct Islands II

Problem Restatement We are given a binary grid. Value Meaning 1 Land 0 Water An island is a group of connected land cells using 4-directional movement: up down left right We need to count how many distinct island shapes exist. Two islands are considered the same if one can be transformed into the other using: Allowed Transformation Rotation Reflection Translation This means two islands are identical if we can rotate...

Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 812: Largest Triangle Area

Problem Restatement We are given an array of unique points on the X-Y plane. Each point is written as: [x, y] We need to choose any three different points and form a triangle. Return the largest possible triangle area. Answers within 10^-5 of the actual answer are accepted. The constraints are small: 3 <= points.length <= 50 , and each coordinate is between -50 and 50 . Input and Output...

Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 883: Projection Area of 3D Shapes

Problem Restatement We are given an n x n grid. Each cell: grid[r][c] contains a vertical stack of cubes. We want the total projection area of the 3D shape onto three planes: Projection Meaning Top view Looking down from above Front view Looking from the front Side view Looking from the side Return the sum of these three projection areas. The official problem defines each cube as a 1 x...

Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 858: Mirror Reflection

Problem Restatement We have a square room with mirrored walls. The side length of the room is p . A laser starts from the southwest corner. It first hits the east wall at a distance q from receptor 0 . There are three receptors: Receptor Corner 0 Southeast corner 1 Northeast corner 2 Northwest corner The southwest corner has no receptor. The laser reflects from the mirrors until it reaches...

Practice › LeetCode › LeetCode (archived) › LeetCode 06xx ›

LeetCode 612: Shortest Distance in a Plane

Problem Restatement We are given a table called Point2D . Each row represents one point in a 2D plane. Column Type Meaning x decimal x-coordinate y decimal y-coordinate We need to find the shortest Euclidean distance between any two distinct points. The result should contain one column: Column Meaning shortest Minimum distance between any pair of points The final answer should be rounded to two decimal places. The official problem...

Practice › LeetCode › LeetCode (archived) › LeetCode 05xx ›

LeetCode 593: Valid Square

Problem Restatement We are given four points in 2D space: p1, p2, p3, p4 Each point is represented as: [x, y] We need to return True if these four points form a valid square. The points are not given in any particular order. A valid square has four equal sides with positive length and four right angles. The coordinates satisfy -10^4 <= x_i, y_i <= 10^4 . ( leetcode.com ,...

Practice › LeetCode › LeetCode (archived) › LeetCode 05xx ›

LeetCode 587: Erect the Fence

Problem Restatement We are given an array trees , where each tree is represented by a point: [x, y] We need to build the shortest fence that encloses all trees. Return the coordinates of all trees that lie exactly on the fence perimeter. This is a convex hull problem. The important detail is that trees on straight boundary edges must also be included, not only the corner points. The input...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 469: Convex Polygon

Problem Restatement We are given a list of points in the 2D plane. The points are already ordered around the polygon. Connecting them sequentially forms a simple polygon. That means the edges do not cross each other except at shared vertices. We need to return whether the polygon is convex. A polygon is convex if it always turns in the same direction as we walk around its boundary. The problem...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 447: Number of Boomerangs

Problem Restatement We are given a list of distinct points on a 2D plane. Each point is represented as: [x, y] A boomerang is an ordered tuple of points: (i, j, k) such that the distance from i to j equals the distance from i to k . The order matters. So: (i, j, k) and: (i, k, j) are counted as two different boomerangs. The official problem states that...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 497: Random Point in Non-overlapping Rectangles

Problem Restatement We are given a list of non-overlapping axis-aligned rectangles. Each rectangle is represented as: [x1, y1, x2, y2] where: Value Meaning x1, y1 Bottom-left corner x2, y2 Top-right corner All coordinates are integers. We need to implement a class that can randomly return an integer point inside the area covered by the rectangles. A point on the border is included. Every valid integer point across all rectangles must...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 223: Rectangle Area

Problem Restatement We are given two axis-aligned rectangles in a 2D plane. The first rectangle is defined by: (ax1, ay1) (ax2, ay2) The second rectangle is defined by: (bx1, by1) (bx2, by2) Each pair represents the bottom-left corner and top-right corner of a rectangle. We need to return the total area covered by both rectangles. If the rectangles overlap, the overlapping region should be counted only once. The official statement...

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 391: Perfect Rectangle

Problem Restatement We are given a list of axis-aligned rectangles. Each rectangle is represented as: [xi, yi, ai, bi] where: (xi, yi) is the bottom-left corner (ai, bi) is the top-right corner We need to return True if all small rectangles together form one exact rectangular region. That means: There must be no gaps. There must be no overlaps. The final union must be one rectangle. Input and Output Item...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 218: The Skyline Problem

Problem Restatement We are given a list of buildings. Each building is represented as: [left, right, height] Meaning: Field Meaning left Left x-coordinate right Right x-coordinate height Building height We need to return the skyline formed by these buildings. The skyline is represented as a list of key points: [x, height] Each key point means: at x-coordinate x, the skyline height changes to height The last point must end with...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 149: Max Points on a Line

Problem Restatement We are given a list of 2D points: points[i] = [xi, yi] Return the maximum number of points that lie on the same straight line. A line may be horizontal, vertical, diagonal, or any slope. LeetCode constrains the number of points to at most 300 , which allows an O(n^2) solution. Examples Example 1: points = [[1,1],[2,2],[3,3]] All three points lie on: y = x Output: 3 Example...

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 335: Self Crossing

Problem Restatement We are given an integer array distance . We start at point (0, 0) on a 2D plane. The movement directions repeat in this order: north -> west -> south -> east -> north -> ... After each move, the direction turns counter-clockwise. Return true if the path crosses itself. Otherwise, return false . The problem asks for a one-pass algorithm using O(1) extra space. The official statement...

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 356: Line Reflection

Problem Restatement We are given a list of points on a 2D plane. Each point is represented as: [x, y] We need to decide whether there exists a vertical line such that reflecting every point across that line gives the same set of points. A vertical line has this form: x = c The line is parallel to the y-axis. When a point (x, y) is reflected across x =...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 478: Generate Random Point in a Circle

Problem Restatement We are given a circle defined by: Value Meaning radius Radius of the circle x_center x-coordinate of the center y_center y-coordinate of the center We need to implement a class with two parts: Method Meaning Solution(radius, x_center, y_center) Stores the circle randPoint() Returns a random point inside or on the circle The returned point must be uniformly distributed inside the circle. A point on the circumference is allowed....

Maths › 03. Logic and Foundations ›

4.5 Examples

Model theory treats many familiar mathematical objects as structures for suitable first order languages, and this viewpoint allows groups, rings, fields, ordered sets, graphs, and geometric systems to be studied using a common formal framework. Algebraic Structures Algebraic structures are among the most natural examples of first order structures, because they are usually described by a domain together with operations and distinguished constants. A group may be represented in the...

Maths ›

52. Convex and Discrete Geometry

This volume studies convex sets, polytopes, and discrete geometric structures. It emphasizes combinatorial structure, geometric inequalities, and computational aspects. Part I. Convex Sets Chapter 1. Convexity 1.1 Convex sets and combinations 1.2 Convex hulls 1.3 Extreme points 1.4 Carathéodory theorem 1.5 Examples Chapter 2. Separation and Support 2.1 Supporting hyperplanes 2.2 Separation theorems 2.3 Dual cones 2.4 Applications 2.5 Examples Chapter 3. Convex Functions 3.1 Definitions 3.2 Properties 3.3 Jensen...

Maths ›

51. Geometry

This volume studies geometric structures, transformations, and invariants. It covers classical geometry, synthetic methods, and modern structural viewpoints. Part I. Foundations of Geometry Chapter 1. Geometric Objects 1.1 Points, lines, planes 1.2 Incidence and betweenness 1.3 Distance and angle 1.4 Congruence and similarity 1.5 Examples Chapter 2. Axiomatic Geometry 2.1 Euclidean axioms 2.2 Hilbert-style axioms 2.3 Models of geometry 2.4 Independence of axioms 2.5 Examples Chapter 3. Transformations 3.1 Isometries...

Maths ›

53. Differential Geometry

This volume studies smooth geometric structures using calculus. It develops curves, surfaces, manifolds, and curvature, forming the foundation for modern geometry and physics. Part I. Curves and Surfaces Chapter 1. Curves in Euclidean Space 1.1 Parametrized curves 1.2 Arc length 1.3 Curvature and torsion 1.4 Frenet frame 1.5 Examples Chapter 2. Surfaces 2.1 Parametrized surfaces 2.2 Tangent planes 2.3 First fundamental form 2.4 Surface area 2.5 Examples Chapter 3. Curvature...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2023 Shortlist ›

IMO 2023 Shortlist G6

IMO 2023 Shortlist G6 Category: Geometry Problem Let ABC be an acute-angled triangle with circumcircle ω. A circle Γ is internally tangent to ω at A and also tangent to BC at D. Let AB and AC intersect Γ at P and Q respectively. Let M and N be points on line BC such that B is the midpoint of DM and C is the midpoint of DN. Lines MP...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2006 Shortlist ›

IMO 2006 Shortlist G4

IMO 2006 Shortlist G4 Category: Geometry Problem A point D is chosen on the side AC of a triangle ABC with ∠C < ∠A < 90◦ in such a way that BD = BA. The incircle of ABC is tangent to AB and AC at points K and L, respectively. Let J be the incentre of triangle BCD. Prove that the line KL intersects the line segment AJ at its...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2019 Shortlist ›

IMO 2019 Shortlist G1

IMO 2019 Shortlist G1 Category: Geometry Problem Let ABC be a triangle. Circle Γ passes through A, meets segments AB and AC again at points D and E respectively, and intersects segment BC at F and G such that F lies between B and G. The tangent to circle BDF at F and the tangent to circle CEG at G meet at point T. Suppose that points A and T...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2014 Shortlist ›

IMO 2014 Shortlist G4

IMO 2014 Shortlist G4 Category: Geometry Problem Consider a fixed circle Γ with three fixed points A, B, and C on it. Also, let us fix a real number λ P p0,1q. For a variable point P R tA,B,Cu on Γ, let M be the point on the segment CP such that CM “ λ ¨ CP. Let Q be the second point of intersection of the circumcircles of the...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2012 Shortlist ›

IMO 2012 Shortlist G5

IMO 2012 Shortlist G5 Category: Geometry Problem Let ABC be a triangle with ∠BCA = 90◦ , and let C0 be the foot of the altitude from C. Choose a point X in the interior of the segment CC0, and let K,L be the points on the segments AX,BX for which BK = BC and AL = AC respectively. Denote by M the intersection of AL and BK. Show that...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2023 Shortlist ›

IMO 2023 Shortlist G5

IMO 2023 Shortlist G5 Category: Geometry Problem Let ABC be an acute-angled triangle with circumcircle ω and circumcentre O. Points D ‰ B and E ‰ C lie on ω such that BD K AC and CE K AB. Let CO meet AB at X, and BO meet AC at Y . Prove that the circumcircles of triangles BXD and CY E have an intersection on line AO. (Malaysia)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2007 Shortlist ›

IMO 2007 Shortlist G7

IMO 2007 Shortlist G7 Category: Geometry Problem Given an acute triangle ABC with angles α, β and γ at vertices A, B and C, respectively, such that β > γ. Point I is the incenter, and R is the circumradius. Point D is the foot of the altitude from vertex A. Point K lies on line AD such that AK = 2R, and D separates A and K. Finally, lines...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2007 Shortlist ›

IMO 2007 Shortlist G4

IMO 2007 Shortlist G4 Category: Geometry Problem Consider five points A, B, C, D, E such that ABCD is a parallelogram and BCED is a cyclic quadrilateral. Let be a line passing through A, and let intersect segment DC and line BC at points F and G, respectively. Suppose that EF = EG = EC. Prove that ` is the bisector of angle DAB. (Luxembourg)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2010 Shortlist ›

IMO 2010 Shortlist G1

IMO 2010 Shortlist G1 Category: Geometry Problem Let ABC be an acute triangle with D,E,F the feet of the altitudes lying on BC,CA,AB respectively. One of the intersection points of the line EF and the circumcircle is P. The lines BP and DF meet at point Q. Prove that AP AQ. (United Kingdom)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2017 Shortlist ›

IMO 2017 Shortlist G8

IMO 2017 Shortlist G8 Category: Geometry Problem There are 2017 mutually external ir les drawn on a bla kboard, su h that no two are tangent and no three share a ommon tangent. A tangent segment is a line segment that is a ommon tangent to two ir les, starting at one tangent point and ending at the other one. Lu iano is drawing tangent segments on the bla kboard,...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2011 Shortlist ›

IMO 2011 Shortlist G6

IMO 2011 Shortlist G6 Category: Geometry Problem Let ABC be a triangle with AB = AC, and let D be the midpoint of AC. The angle bisector of ∠BAC intersects the circle through D, B, and C in a point E inside the triangle ABC. The line BD intersects the circle through A, E, and B in two points B and F. The lines AF and BE meet at a...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2008 Shortlist ›

IMO 2008 Shortlist G1

IMO 2008 Shortlist G1 Category: Geometry Problem In an acute-angled triangle ABC, point H is the orthocentre and A0, B0, C0 are the midpoints of the sides BC, CA, AB, respectively. Consider three circles passing through H: ωa around A0, ωb around B0 and ωc around C0. The circle ωa intersects the line BC at A1 and A2; ωb intersects CA at B1 and B2; ωc intersects AB at C1...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2014 Shortlist ›

IMO 2014 Shortlist G5

IMO 2014 Shortlist G5 Category: Geometry Problem Let ABCD be a convex quadrilateral with =B “ =D “ 90˝ . Point H is the foot of the perpendicular from A to BD. The points S and T are chosen on the sides AB and AD, respectively, in such a way that H lies inside triangle SCT and =SHC ´ =BSC “ 90˝ , =THC ´ =DTC “ 90˝ . Prove...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2013 Shortlist ›

IMO 2013 Shortlist G4

IMO 2013 Shortlist G4 Category: Geometry Problem Let ABC be a triangle with =B ą =C. Let P and Q be two different points on line AC such that =PBA “ =QBA “ =ACB and A is located between P and C. Suppose that there exists an interior point D of segment BQ for which PD “ PB. Let the ray AD intersect the circle ABC at R ‰ A....

Practice › Mathematics › IMO › IMO Shortlist › IMO 2022 Shortlist ›

IMO 2022 Shortlist G7

IMO 2022 Shortlist G7 Category: Geometry Problem Let ABC and A1 B1 C1 be two triangles having the same circumcircle ω, and the same orthocentre H. Let Ω be the circumcircle of the triangle determined by the lines AA1 , BB1 and CC1 . Prove that H, the centre of ω, and the centre of Ω are collinear. (Denmark)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2023 Shortlist ›

IMO 2023 Shortlist G2

IMO 2023 Shortlist G2 Category: Geometry Problem Let ABC be a triangle with AC ą BC. Let ω be the circumcircle of triangle ABC and let r be the radius of ω. Point P lies on segment AC such that BC “ CP and point S is the foot of the perpendicular from P to line AB. Let ray BP intersect ω again at D and let Q lie on...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2008 Shortlist ›

IMO 2008 Shortlist G7

IMO 2008 Shortlist G7 Category: Geometry Problem Let ABCD be a convex quadrilateral with AB 6= BC. Denote by ω1 and ω2 the incircles of triangles ABC and ADC. Suppose that there exists a circle ω inscribed in angle ABC, tangent to the extensions of line segments AD and CD. Prove that the common external tangents of ω1 and ω2 intersect on ω.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2022 Shortlist ›

IMO 2022 Shortlist G5

IMO 2022 Shortlist G5 Category: Geometry Problem Let ABC be a triangle, and let 1 and 2 be two parallel lines. For i “ 1,2, let `i meet the lines BC, CA, and AB at Xi, Yi, and Zi, respectively. Suppose that the line through Xi perpendicular to BC, the line through Yi perpendicular to CA, and finally the line through Zi perpendicular to AB, determine a non-degenerate triangle ∆i....

Practice › Mathematics › IMO › IMO Shortlist › IMO 2022 Shortlist ›

IMO 2022 Shortlist G2

IMO 2022 Shortlist G2 Category: Geometry Problem In the acute-angled triangle ABC, the point F is the foot of the altitude from A, and P is a point on the segment AF. The lines through P parallel to AC and AB meet BC at D and E, respectively. Points X ‰ A and Y ‰ A lie on the circles ABD and ACE, respectively, such that DA “ DX and...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2020 Shortlist ›

IMO 2020 Shortlist G5

IMO 2020 Shortlist G5 Category: Geometry Problem Let ABCD be a cyclic quadrilateral with no two sides parallel. Let K, L, M, and N be points lying on sides AB, BC, CD, and DA, respectively, such that KLMN is a rhombus with KL k AC and LM k BD. Let ω1, ω2, ω3, and ω4 be the incircles of triangles ANK, BKL, CLM, and DMN, respectively. Prove that the internal...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2020 Shortlist ›

IMO 2020 Shortlist G4

IMO 2020 Shortlist G4 Category: Geometry Problem In the plane, there are n ě 6 pairwise disjoint disks D1,D2,...,Dn with radii R1 ě R2 ě ... ě Rn. For every i “ 1,2,...,n, a point Pi is chosen in disk Di. Let O be an arbitrary point in the plane. Prove that OP1 OP2 ... OPn ě R6 R7 ... Rn. (A disk is assumed to contain its boundary.) (Iran)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2007 Shortlist ›

IMO 2007 Shortlist G6

IMO 2007 Shortlist G6 Category: Geometry Problem Determine the smallest positive real number k with the following property. Let ABCD be a convex quadrilateral, and let points A1, B1, C1 and D1 lie on sides AB, BC, CD and DA, respectively. Consider the areas of triangles AA1D1, BB1A1, CC1B1, and DD1C1; let S be the sum of the two smallest ones, and let S1 be the area of quadrilateral A1B1C1D1....

Practice › Mathematics › IMO › IMO Shortlist › IMO 2008 Shortlist ›

IMO 2008 Shortlist G4

IMO 2008 Shortlist G4 Category: Geometry Problem In an acute triangle ABC segments BE and CF are altitudes. Two circles passing through the points A and F are tangent to the line BC at the points P and Q so that B lies between C and Q. Prove that the lines PE and QF intersect on the circumcircle of triangle AEF.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2006 Shortlist ›

IMO 2006 Shortlist G10

IMO 2006 Shortlist G10 Category: Geometry Problem To each side a of a convex polygon we assign the maximum area of a triangle contained in the polygon and having a as one of its sides. Show that the sum of the areas assigned to all sides of the polygon is not less than twice the area of the polygon. (Serbia)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2021 Shortlist ›

IMO 2021 Shortlist G1

IMO 2021 Shortlist G1 Category: Geometry Problem Let ABCD be a parallelogram such that AC “ BC. A point P is chosen on the extension of the segment AB beyond B. The circumcircle of the triangle ACD meets the segment PD again at Q, and the circumcircle of the triangle APQ meets the segment PC again at R. Prove that the lines CD, AQ, and BR are concurrent.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2009 Shortlist ›

IMO 2009 Shortlist G3

IMO 2009 Shortlist G3 Category: Geometry Problem Let ABC be a triangle. The incircle of ABC touches the sides AB and AC at the points Z and Y , respectively. Let G be the point where the lines BY and CZ meet, and let R and S be points such that the two quadrilaterals BCY R and BCSZ are parallelograms. Prove that GR = GS.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2007 Shortlist ›

IMO 2007 Shortlist G1

IMO 2007 Shortlist G1 Category: Geometry Problem In triangle ABC, the angle bisector at vertex C intersects the circumcircle and the per- pendicular bisectors of sides BC and CA at points R, P, and Q, respectively. The midpoints of BC and CA are S and T, respectively. Prove that triangles RQT and RPS have the same area. (Czech Republic)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2022 Shortlist ›

IMO 2022 Shortlist G3

IMO 2022 Shortlist G3 Category: Geometry Problem Let ABCD be a cyclic quadrilateral. Assume that the points Q, A, B, P are collinear in this order, in such a way that the line AC is tangent to the circle ADQ, and the line BD is tangent to the circle BCP. Let M and N be the midpoints of BC and AD, respectively. Prove that the following three lines are concurrent:...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2010 Shortlist ›

IMO 2010 Shortlist G5

IMO 2010 Shortlist G5 Category: Geometry Problem Let ABCDE be a convex pentagon such that BC k AE, AB BC AE, and =ABC =CDE. Let M be the midpoint of CE, and let O be the circumcenter of triangle BCD. Given that =DMO 90, prove that 2=BDA =CDE. (Ukraine)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2016 Shortlist ›

IMO 2016 Shortlist G8

IMO 2016 Shortlist G8 Category: Geometry Problem Let A1,B1 and C1 be points on sides BC,CA and AB of an acute triangle ABC respectively, such that AA1,BB1 and CC1 are the internal angle bisectors of triangle ABC. Let I be the incentre of triangle ABC, and H be the orthocentre of triangle A1B1C1. Show that AH + BH + CH ⩾ AI + BI + CI. Shortlisted problems 9

Practice › Mathematics › IMO › IMO Shortlist › IMO 2016 Shortlist ›

IMO 2016 Shortlist G3

IMO 2016 Shortlist G3 Category: Geometry Problem Let B = (−1,0) and C = (1,0) be fixed points on the coordinate plane. A nonempty, bounded subset S of the plane is said to be nice if (i) there is a point T in S such that for every point Q in S, the segment TQ lies entirely in S; and (ii) for any triangle P1P2P3, there exists a unique point...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2019 Shortlist ›

IMO 2019 Shortlist G5

IMO 2019 Shortlist G5 Category: Geometry Problem Let ABCDE be a convex pentagon with CD “ DE and =EDC ‰ 2 ¨ =ADB. Suppose that a point P is located in the interior of the pentagon such that AP “ AE and BP “ BC. Prove that P lies on the diagonal CE if and only if areapBCDq areapADEq “ areapABDq areapABPq. (Hungary)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2016 Shortlist ›

IMO 2016 Shortlist G4

IMO 2016 Shortlist G4 Category: Geometry Problem Let ABC be a triangle with AB = AC 6= BC and let I be its incentre. The line BI meets AC at D, and the line through D perpendicular to AC meets AI at E. Prove that the reflection of I in AC lies on the circumcircle of triangle BDE.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2021 Shortlist ›

IMO 2021 Shortlist G2

IMO 2021 Shortlist G2 Category: Geometry Problem Let ABCD be a convex quadrilateral circumscribed around a circle with centre I. Let ω be the circumcircle of the triangle ACI. The extensions of BA and BC beyond A and C meet ω at X and Z, respectively. The extensions of AD and CD beyond D meet ω at Y and T, respectively. Prove that the perimeters of the (possibly self-intersecting) quadrilaterals...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2016 Shortlist ›

IMO 2016 Shortlist G7

IMO 2016 Shortlist G7 Category: Geometry Problem Let I be the incentre of a non-equilateral triangle ABC, IA be the A-excentre, I0 A be the reflection of IA in BC, and lA be the reflection of line AI0 A in AI. Define points IB,I0 B and line lB analogously. Let P be the intersection point of lA and lB. (a) Prove that P lies on line OI where O is...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2021 Shortlist ›

IMO 2021 Shortlist G4

IMO 2021 Shortlist G4 Category: Geometry Problem Let ABCD be a quadrilateral inscribed in a circle Ω. Let the tangent to Ω at D intersect the rays BA and BC at points E and F, respectively. A point T is chosen inside the triangle ABC so that TE k CD and TF k AD. Let K ‰ D be a point on the segment DF such that TD “TK. Prove...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2010 Shortlist ›

IMO 2010 Shortlist G2

IMO 2010 Shortlist G2 Category: Geometry Problem Point P lies inside triangle ABC. Lines AP, BP, CP meet the circumcircle of ABC again at points K, L, M, respectively. The tangent to the circumcircle at C meets line AB at S. Prove that SC SP if and only if MK ML. (Poland)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2018 Shortlist ›

IMO 2018 Shortlist G4

IMO 2018 Shortlist G4 Category: Geometry Problem A point T is hosen inside a triangle ABC. Let A1, B1, and C1 be the ree tions of T in BC, CA, and AB, respe tively. Let Ω be the ir um ir le of the triangle A1B1C1. The lines A1T, B1T, and C1T meet Ω again at A2, B2, and C2, respe tively. Prove that the lines AA2, BB2, and CC2...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2006 Shortlist ›

IMO 2006 Shortlist G3

IMO 2006 Shortlist G3 Category: Geometry Problem Let ABCDE be a convex pentagon such that ∠BAC = ∠CAD = ∠DAE and ∠ABC = ∠ACD = ∠ADE. The diagonals BD and CE meet at P. Prove that the line AP bisects the side CD. (USA)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2008 Shortlist ›

IMO 2008 Shortlist G5

IMO 2008 Shortlist G5 Category: Geometry Problem Let k and n be integers with 0 ≤ k ≤ n−2. Consider a set L of n lines in the plane such that no two of them are parallel and no three have a common point. Denote by I the set of intersection points of lines in L. Let O be a point in the plane not lying on any line of...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2010 Shortlist ›

IMO 2010 Shortlist G7

IMO 2010 Shortlist G7 Category: Geometry Problem Three circular arcs γ1, γ2, and γ3 connect the points A and C. These arcs lie in the same half-plane defined by line AC in such a way that arc γ2 lies between the arcs γ1 and γ3. Point B lies on the segment AC. Let h1, h2, and h3 be three rays starting at B, lying in the same half-plane, h2 being...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2012 Shortlist ›

IMO 2012 Shortlist G4

IMO 2012 Shortlist G4 Category: Geometry Problem Let ABC be a triangle with AB 6= AC and circumcenter O. The bisector of ∠BAC intersects BC at D. Let E be the reflection of D with respect to the midpoint of BC. The lines through D and E perpendicular to BC intersect the lines AO and AD at X and Y respectively. Prove that the quadrilateral BXCY is cyclic. Solution. The...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2019 Shortlist ›

IMO 2019 Shortlist G2

IMO 2019 Shortlist G2 Category: Geometry Problem Let ABC be an acute-angled triangle and let D, E, and F be the feet of altitudes from A, B, and C to sides BC, CA, and AB, respectively. Denote by ωB and ωC the incircles of triangles BDF and CDE, and let these circles be tangent to segments DF and DE at M and N, respectively. Let line MN meet circles ωB...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2010 Shortlist ›

IMO 2010 Shortlist G6

IMO 2010 Shortlist G6 Category: Geometry Problem The vertices X, Y , Z of an equilateral triangle XY Z lie respectively on the sides BC, CA, AB of an acute-angled triangle ABC. Prove that the incenter of triangle ABC lies inside triangle XY Z.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2006 Shortlist ›

IMO 2006 Shortlist G7

IMO 2006 Shortlist G7 Category: Geometry Problem In a triangle ABC, let Ma,Mb,Mc be respectively the midpoints of the sides BC, CA, AB and Ta,Tb,Tc be the midpoints of the arcs BC, CA, AB of the circumcircle of ABC, not containing the opposite vertices. For i ∈ {a,b,c}, let ωi be the circle with MiTi as diameter. Let pi be the common external tangent to ωj, ωk ({i,j,k} = {a,b,c})...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2006 Shortlist ›

IMO 2006 Shortlist G5

IMO 2006 Shortlist G5 Category: Geometry Problem In triangle ABC, let J be the centre of the excircle tangent to side BC at A1 and to the extensions of sides AC and AB at B1 and C1, respectively. Suppose that the lines A1B1 and AB are perpendicular and intersect at D. Let E be the foot of the perpendicular from C1 to line DJ. Determine the angles ∠BEA1 and ∠AEB1....

Practice › Mathematics › IMO › IMO Shortlist › IMO 2015 Shortlist ›

IMO 2015 Shortlist G3

IMO 2015 Shortlist G3 Category: Geometry Problem Let ABC be a triangle with =C “ 900 , and let H be the foot of the altitude from C. A point D is chosen inside the triangle CBH so that CH bisects AD. Let P be the intersection point of the lines BD and CH. Let ω be the semicircle with diameter BD that meets the segment CB at an interior...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2024 Shortlist ›

IMO 2024 Shortlist G1

IMO 2024 Shortlist G1 Category: Geometry Problem Let ABCD be a cyclic quadrilateral such that AC ă BD ă AD and =DBA ă 90˝ . Point E lies on the line through D parallel to AB such that E and C lie on opposite sides of line AD, and AC “ DE. Point F lies on the line through A parallel to CD such that F and C lie on...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2015 Shortlist ›

IMO 2015 Shortlist G2

IMO 2015 Shortlist G2 Category: Geometry Problem Let ABC be a triangle inscribed into a circle Ω with center O. A circle Γ with center A meets the side BC at points D and E such that D lies between B and E. Moreover, let F and G be the common points of Γ and Ω. We assume that F lies on the arc AB of Ω not containing C,...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2012 Shortlist ›

IMO 2012 Shortlist G3

IMO 2012 Shortlist G3 Category: Geometry Problem In an acute triangle ABC the points D, E and F are the feet of the altitudes through A, B and C respectively. The incenters of the triangles AEF and BDF are I1 and I2 respectively; the circumcenters of the triangles ACI1 and BCI2 are O1 and O2 respectively. Prove that I1I2 and O1O2 are parallel. Solution. Let ∠CAB = α, ∠ABC =...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2010 Shortlist ›

IMO 2010 Shortlist G61

IMO 2010 Shortlist G61 Category: Geometry Problem . The vertices X, Y , Z of an equilateral triangle XY Z lie respectively on the sides BC, CA, AB of a triangle ABC. Prove that if the incenter of triangle ABC lies outside triangle XY Z, then one of the angles of triangle ABC is greater than 120. (Bulgaria)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2022 Shortlist ›

IMO 2022 Shortlist G8

IMO 2022 Shortlist G8 Category: Geometry Problem Let AA1 BCC1 B1 be a convex cyclic hexagon such that AC is tangent to the incircle of the triangle A1 B1 C1 , and A1 C1 is tangent to the incircle of the triangle ABC. Let the lines AB and A1 B1 meet at X and let the lines BC and B1 C1 meet at Y . Prove that if XBY B1...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2008 Shortlist ›

IMO 2008 Shortlist G2

IMO 2008 Shortlist G2 Category: Geometry Problem Given trapezoid ABCD with parallel sides AB and CD, assume that there exist points E on line BC outside segment BC, and F inside segment AD, such that ∠DAE = ∠CBF. Denote by I the point of intersection of CD and EF, and by J the point of intersection of AB and EF. Let K be the midpoint of segment EF; assume it...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2015 Shortlist ›

IMO 2015 Shortlist G7

IMO 2015 Shortlist G7 Category: Geometry Problem Let ABCD be a convex quadrilateral, and let P, Q, R, and S be points on the sides AB, BC, CD, and DA, respectively. Let the line segments PR and QS meet at O. Suppose that each of the quadrilaterals APOS, BQOP, CROQ, and DSOR has an incircle. Prove that the lines AC, PQ, and RS are either concurrent or parallel to each...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2006 Shortlist ›

IMO 2006 Shortlist G1

IMO 2006 Shortlist G1 Category: Geometry Problem Let ABC be a triangle with incentre I. A point P in the interior of the triangle satisfies ∠PBA + ∠PCA = ∠PBC + ∠PCB. Show that AP ≥ AI and that equality holds if and only if P coincides with I. (Korea)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2017 Shortlist ›

IMO 2017 Shortlist G7

IMO 2017 Shortlist G7 Category: Geometry Problem A onvex quadrilateral ABCD has an ins ribed ir le with enter I. Let Ia, Ib, Ic, and Id be the in enters of the triangles DAB, ABC, BCD, and CDA, respe tively. Suppose that the ommon external tangents of the ir les AIbId and CIbId meet at X, and the ommon external tangents of the ir les BIaIc and DIaIc meet at...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2020 Shortlist ›

IMO 2020 Shortlist G3

IMO 2020 Shortlist G3 Category: Geometry Problem Let ABCD be a convex quadrilateral with =ABC ą 90˝ , =CDA ą 90˝ , and =DAB “ =BCD. Denote by E and F the reflections of A in lines BC and CD, respectively. Suppose that the segments AE and AF meet the line BD at K and L, respectively. Prove that the circumcircles of triangles BEK and DFL are tangent to each...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2014 Shortlist ›

IMO 2014 Shortlist G2

IMO 2014 Shortlist G2 Category: Geometry Problem Let ABC be a triangle. The points K, L, and M lie on the segments BC, CA, and AB, respectively, such that the lines AK, BL, and CM intersect in a common point. Prove that it is possible to choose two of the triangles ALM, BMK, and CKL whose inradii sum up to at least the inradius of the triangle ABC. (Estonia)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2009 Shortlist ›

IMO 2009 Shortlist G6

IMO 2009 Shortlist G6 Category: Geometry Problem Let the sides AD and BC of the quadrilateral ABCD (such that AB is not parallel to CD) intersect at point P. Points O1 and O2 are the circumcenters and points H1 and H2 are the orthocenters of triangles ABP and DCP, respectively. Denote the midpoints of segments O1H1 and O2H2 by E1 and E2, respectively. Prove that the perpendicular from E1 on...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2009 Shortlist ›

IMO 2009 Shortlist G7

IMO 2009 Shortlist G7 Category: Geometry Problem Let ABC be a triangle with incenter I and let X, Y and Z be the incenters of the triangles BIC, CIA and AIB, respectively. Let the triangle XY Z be equilateral. Prove that ABC is equilateral too.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2019 Shortlist ›

IMO 2019 Shortlist G8

IMO 2019 Shortlist G8 Category: Geometry Problem Let L be the set of all lines in the plane and let f be a function that assigns to each line ℓ P L a point fpℓq on ℓ. Suppose that for any point X, and for any three lines ℓ1, ℓ2, ℓ3 passing through X, the points fpℓ1q, fpℓ2q, fpℓ3q and X lie on a circle. Prove that there is a...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2018 Shortlist ›

IMO 2018 Shortlist G5

IMO 2018 Shortlist G5 Category: Geometry Problem Let ABC be a triangle with ir um ir le ω and in entre I. A line ℓ interse ts the lines AI, BI, and CI at points D, E, and F, respe tively, distin t from the points A, B, C, and I. The perpendi ular bise tors x, y, and z of the segments AD, BE, and CF, respe tively determine...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2012 Shortlist ›

IMO 2012 Shortlist G7

IMO 2012 Shortlist G7 Category: Geometry Problem Let ABCD be a convex quadrilateral with non-parallel sides BC and AD. Assume that there is a point E on the side BC such that the quadrilaterals ABED and AECD are circumscribed. Prove that there is a point F on the side AD such that the quadrilaterals ABCF and BCDF are circumscribed if and only if AB is parallel to CD. Solution. Let...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2006 Shortlist ›

IMO 2006 Shortlist G9

IMO 2006 Shortlist G9 Category: Geometry Problem Points A1,B1,C1 are chosen on the sides BC, CA, AB of a triangle ABC, respectively. The circumcircles of triangles AB1C1, BC1A1, CA1B1 intersect the circumcircle of triangle ABC again at points A2,B2,C2, respectively (A2 6= A, B2 6= B, C2 6= C). Points A3,B3,C3 are symmetric to A1,B1,C1 with respect to the midpoints of the sides BC, CA, AB respectively. Prove that the...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2006 Shortlist ›

IMO 2006 Shortlist G6

IMO 2006 Shortlist G6 Category: Geometry Problem Circles ω1 and ω2 with centres O1 and O2 are externally tangent at point D and internally tangent to a circle ω at points E and F, respectively. Line t is the common tangent of ω1 and ω2 at D. Let AB be the diameter of ω perpendicular to t, so that A, E and O1 are on the same side of t....

Practice › Mathematics › IMO › IMO Shortlist › IMO 2010 Shortlist ›

IMO 2010 Shortlist G4

IMO 2010 Shortlist G4 Category: Geometry Problem Let I be the incenter of a triangle ABC and Γ be its circumcircle. Let the line AI intersect Γ at a point D A. Let F and E be points on side BC and arc BDC respectively such that =BAF =CAE 1 =BAC. Finally, let G be the midpoint of the segment IF. Prove that the lines DG and EI...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2011 Shortlist ›

IMO 2011 Shortlist G2

IMO 2011 Shortlist G2 Category: Geometry Problem Let A1A2A3A4 be a non-cyclic quadrilateral. Let O1 and r1 be the circumcenter and the circumradius of the triangle A2A3A4. Define O2, O3, O4 and r2, r3, r4 in a similar way. Prove that O1A2 1 − r2 + O2A2 2 − r2 + O3A2 3 − r2 + O4A2 4 − r2 = 0.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2018 Shortlist ›

IMO 2018 Shortlist G6

IMO 2018 Shortlist G6 Category: Geometry Problem A onvex quadrilateral ABCD satises AB ¨ CD “ BC ¨ DA. A point X is hosen inside the quadrilateral so that =XAB “ =XCD and =XBC “ =XDA. Prove that =AXB` =CXD “ 180˝ . (Poland)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2019 Shortlist ›

IMO 2019 Shortlist G4

IMO 2019 Shortlist G4 Category: Geometry Problem Let P be a point inside triangle ABC. Let AP meet BC at A1, let BP meet CA at B1, and let CP meet AB at C1. Let A2 be the point such that A1 is the midpoint of PA2, let B2 be the point such that B1 is the midpoint of PB2, and let C2 be the point such that C1 is...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2020 Shortlist ›

IMO 2020 Shortlist G1

IMO 2020 Shortlist G1 Category: Geometry Problem Let ABC be an isosceles triangle with BC “ CA, and let D be a point inside side AB such that AD ă DB. Let P and Q be two points inside sides BC and CA, respectively, such that =DPB “ =DQA “ 90˝ . Let the perpendicular bisector of PQ meet line segment CQ at E, and let the circumcircles of triangles...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2007 Shortlist ›

IMO 2007 Shortlist G8

IMO 2007 Shortlist G8 Category: Geometry Problem Point P lies on side AB of a convex quadrilateral ABCD. Let ω be the incircle of triangle CPD, and let I be its incenter. Suppose that ω is tangent to the incircles of triangles APD and BPC at points K and L, respectively. Let lines AC and BD meet at E, and let lines AK and BL meet at F. Prove that...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2009 Shortlist ›

IMO 2009 Shortlist G8

IMO 2009 Shortlist G8 Category: Geometry Problem Let ABCD be a circumscribed quadrilateral. Let g be a line through A which meets the segment BC in M and the line CD in N. Denote by I1, I2, and I3 the incenters of 4ABM, 4MNC, and 4NDA, respectively. Show that the orthocenter of 4I1I2I3 lies on g.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2017 Shortlist ›

IMO 2017 Shortlist G1

IMO 2017 Shortlist G1 Category: Geometry Problem Let ABCDE be a onvex pentagon su h that AB “ BC “ CD, =EAB “ =BCD, and =EDC “ =CBA. Prove that the perpendi ular line from E to BC and the line seg- ments AC and BD are on urrent. (Italy)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2018 Shortlist ›

IMO 2018 Shortlist G7

IMO 2018 Shortlist G7 Category: Geometry Problem Let O be the ir um entre, and Ω be the ir um ir le of an a ute-angled triangle ABC. Let P be an arbitrary point on Ω, distin t from A, B, C, and their antipodes in Ω. Denote the ir um entres of the triangles AOP, BOP, and COP by OA, OB, and OC, respe tively. The lines ℓA, ℓB,...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2020 Shortlist ›

IMO 2020 Shortlist G7

IMO 2020 Shortlist G7 Category: Geometry Problem Let P be a point on the circumcircle of an acute-angled triangle ABC. Let D, E, and F be the reflections of P in the midlines of triangle ABC parallel to BC, CA, and AB, respectively. Denote by ωA, ωB, and ωC the circumcircles of triangles ADP, BEP, and CFP, respectively. Denote by ω the circumcircle of the triangle formed by the perpendicular...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2021 Shortlist ›

IMO 2021 Shortlist G3

IMO 2021 Shortlist G3 Category: Geometry Problem Version 1. Let n be a fixed positive integer, and let S be the set of points px,yq on the Cartesian plane such that both coordinates x and y are nonnegative integers smaller than 2n (thus |S| “ 4n2 ). Assume that F is a set consisting of n2 quadrilaterals such that all their vertices lie in S, and each point in S...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2024 Shortlist ›

IMO 2024 Shortlist G8

IMO 2024 Shortlist G8 Category: Geometry Problem Let ABC be a triangle with AB ă AC ă BC, and let D be a point in the interior of segment BC. Let E be a point on the circumcircle of triangle ABC such that A and E lie on opposite sides of line BC and =BAD “ =EAC. Let I, IB, IC, JB, and JC be the incentres of triangles ABC,...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2011 Shortlist ›

IMO 2011 Shortlist G8

IMO 2011 Shortlist G8 Category: Geometry Problem Let ABC be an acute triangle with circumcircle ω. Let t be a tangent line to ω. Let ta, tb, and tc be the lines obtained by reflecting t in the lines BC, CA, and AB, respectively. Show that the circumcircle of the triangle determined by the lines ta, tb, and tc is tangent to the circle ω.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2024 Shortlist ›

IMO 2024 Shortlist G5

IMO 2024 Shortlist G5 Category: Geometry Problem Let ABC be a triangle with incentre I, and let Ω be the circumcircle of triangle BIC. Let K be a point in the interior of segment BC such that =BAK ă =KAC. The angle bisector of =BKA intersects Ω at points W and X such that A and W lie on the same side of BC, and the angle bisector of =CKA...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2012 Shortlist ›

IMO 2012 Shortlist G6

IMO 2012 Shortlist G6 Category: Geometry Problem Let ABC be a triangle with circumcenter O and incenter I. The points D, E and F on the sides BC, CA and AB respectively are such that BD + BF = CA and CD + CE = AB. The circumcircles of the triangles BFD and CDE intersect at P 6= D. Prove that OP = OI. Solution. By Miquel’s theorem the circles...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2023 Shortlist ›

IMO 2023 Shortlist G7

IMO 2023 Shortlist G7 Category: Geometry Problem Let ABC be an acute, scalene triangle with orthocentre H. Let a be the line through the reflection of B with respect to CH and the reflection of C with respect to BH. Lines b and c are defined similarly. Suppose lines a, b, and c determine a triangle T . Prove that the orthocentre of T , the circumcentre of T and...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2008 Shortlist ›

IMO 2008 Shortlist G3

IMO 2008 Shortlist G3 Category: Geometry Problem Let ABCD be a convex quadrilateral and let P and Q be points in ABCD such that PQDA and QPBC are cyclic quadrilaterals. Suppose that there exists a point E on the line segment PQ such that ∠PAE = ∠QDE and ∠PBE = ∠QCE. Show that the quadrilateral ABCD is cyclic.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2024 Shortlist ›

IMO 2024 Shortlist G2

IMO 2024 Shortlist G2 Category: Geometry Problem Let ABC be a triangle with AB ă AC ă BC, incentre I and incircle ω. Let X be the point in the interior of side BC such that the line through X parallel to AC is tangent to ω. Similarly, let Y be the point in the interior of side BC such that the line through Y parallel to AB is tangent...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2015 Shortlist ›

IMO 2015 Shortlist G6

IMO 2015 Shortlist G6 Category: Geometry Problem Let ABC be an acute triangle with AB ą AC, and let Γ be its circumcircle. Let H, M, and F be the orthocenter of the triangle, the midpoint of BC, and the foot of the altitude from A, respectively. Let Q and K be the two points on Γ that satisfy =AQH “ 900 and =QKH “ 900 . Prove that the...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2023 Shortlist ›

IMO 2023 Shortlist G4

IMO 2023 Shortlist G4 Category: Geometry Problem Let ABC be an acute-angled triangle with AB ă AC. Denote its circumcircle by Ω and denote the midpoint of arc CAB by S. Let the perpendicular from A to BC meet BS and Ω at D and E ‰ A respectively. Let the line through D parallel to BC meet line BE at L and denote the circumcircle of triangle BDL by...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2017 Shortlist ›

IMO 2017 Shortlist G2

IMO 2017 Shortlist G2 Category: Geometry Problem Let R and S be distin t points on ir le Ω, and let t denote the tangent line to Ω at R. Point R1 is the ree tion of R with respe t to S. A point I is hosen on the smaller ar RS of Ω so that the ir um ir le Γ of triangle ISR1 interse ts t at...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2014 Shortlist ›

IMO 2014 Shortlist G7

IMO 2014 Shortlist G7 Category: Geometry Problem Let ABC be a triangle with circumcircle Ω and incentre I. Let the line passing through I and perpendicular to CI intersect the segment BC and the arc BC (not containing A) of Ω at points U and V , respectively. Let the line passing through U and parallel to AI intersect AV at X, and let the line passing through V and...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2006 Shortlist ›

IMO 2006 Shortlist G2

IMO 2006 Shortlist G2 Category: Geometry Problem Let ABCD be a trapezoid with parallel sides AB > CD. Points K and L lie on the line segments AB and CD, respectively, so that AK/KB = DL/LC. Suppose that there are points P and Q on the line segment KL satisfying ∠APB = ∠BCD and ∠CQD = ∠ABC. Prove that the points P, Q, B and C are concyclic. (Ukraine)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2016 Shortlist ›

IMO 2016 Shortlist G1

IMO 2016 Shortlist G1 Category: Geometry Problem In a convex pentagon ABCDE, let F be a point on AC such that ∠FBC = 90◦ . Suppose triangles ABF, ACD and ADE are similar isosceles triangles with ∠FAB = ∠FBA = ∠DAC = ∠DCA = ∠EAD = ∠EDA. Let M be the midpoint of CF. Point X is chosen such that AMXE is a parallelogram. Show that BD,EM and FX are...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2012 Shortlist ›

IMO 2012 Shortlist G2

IMO 2012 Shortlist G2 Category: Geometry Problem Let ABCD be a cyclic quadrilateral whose diagonals AC and BD meet at E. The extensions of the sides AD and BC beyond A and B meet at F. Let G be the point such that ECGD is a parallelogram, and let H be the image of E under reflection in AD. Prove that D, H, F, G are concyclic. Solution. We show...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2014 Shortlist ›

IMO 2014 Shortlist G1

IMO 2014 Shortlist G1 Category: Geometry Problem The points P and Q are chosen on the side BC of an acute-angled triangle ABC so that =PAB “ =ACB and =QAC “ =CBA. The points M and N are taken on the rays AP and AQ, respectively, so that AP “ PM and AQ “ QN. Prove that the lines BM and CN intersect on the circumcircle of the triangle ABC....

Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Range Tree Search

Range Tree Search Range tree search answers orthogonal range queries over points in multiple dimensions. It extends balanced binary search trees by storing secondary structures at each node. For two dimensions, each node in the primary tree stores a secondary tree over the remaining coordinate. Problem Given a set of points $(x, y)$ and a query rectangle: $$ [x_1, x_2] \times [y_1, y_2] $$ return all points such that: $$...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2009 Shortlist ›

IMO 2009 Shortlist G4

IMO 2009 Shortlist G4 Category: Geometry Problem Given a cyclic quadrilateral ABCD, let the diagonals AC and BD meet at E and the lines AD and BC meet at F. The midpoints of AB and CD are G and H, respectively. Show that EF is tangent at E to the circle through the points E, G, and H.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2017 Shortlist ›

IMO 2017 Shortlist G3

IMO 2017 Shortlist G3 Category: Geometry Problem Let O be the ir um enter of an a ute s alene triangle ABC. Line OA interse ts the altitudes of ABC through B and C at P and Q, respe tively. The altitudes meet at H. Prove that the ir um enter of triangle PQH lies on a median of triangle ABC. (Ukraine)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2019 Shortlist ›

IMO 2019 Shortlist G6

IMO 2019 Shortlist G6 Category: Geometry Problem Let I be the incentre of acute-angled triangle ABC. Let the incircle meet BC, CA, and AB at D, E, and F, respectively. Let line EF intersect the circumcircle of the triangle at P and Q, such that F lies between E and P. Prove that =DPA ` =AQD “ =QIP. (Slovakia)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2007 Shortlist ›

IMO 2007 Shortlist G5

IMO 2007 Shortlist G5 Category: Geometry Problem Let ABC be a fixed triangle, and let A1, B1, C1 be the midpoints of sides BC, CA, AB, respectively. Let P be a variable point on the circumcircle. Let lines PA1, PB1, PC1 meet the circumcircle again at A0 , B0 , C0 respectively. Assume that the points A, B, C, A0 , B0 , C0 are distinct, and lines AA0 ,...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2024 Shortlist ›

IMO 2024 Shortlist G6

IMO 2024 Shortlist G6 Category: Geometry Problem Let ABC be an acute triangle with AB ă AC, and let Γ be the circumcircle of ABC. Points X and Y lie on Γ so that XY and BC intersect on the external angle bisector of =BAC. Suppose that the tangents to Γ at X and Y intersect at a point T on the same side of BC as A, and that...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2021 Shortlist ›

IMO 2021 Shortlist G8

IMO 2021 Shortlist G8 Category: Geometry Problem Letω bethecircumcircleofatriangleABC,andletΩA beitsexcirclewhichistangent to the segment BC. Let X and Y be the intersection points of ω and ΩA. Let P and Q be the projections of A onto the tangent lines to ΩA at X and Y , respectively. The tangent line at P to the circumcircle of the triangle APX intersects the tangent line at Q to the circumcircle of the...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2020 Shortlist ›

IMO 2020 Shortlist G8

IMO 2020 Shortlist G8 Category: Geometry Problem Let Γ and I be the circumcircle and the incenter of an acute-angled triangle ABC. Two circles ωB and ωC passing through B and C, respectively, are tangent at I. Let ωB meet the shorter arc AB of Γ and segment AB again at P and M, respectively. Similarly, let ωC meet the shorter arc AC of Γ and segment AC again at...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2017 Shortlist ›

IMO 2017 Shortlist G5

IMO 2017 Shortlist G5 Category: Geometry Problem Let ABCC1B1A1 be a onvex hexagon su h that AB “ BC, and suppose that the line segments AA1, BB1, and CC1 have the same perpendi ular bise tor. Let the diagonals AC1 and A1C meet at D, and denote by ω the ir le ABC. Let ω interse t the ir le A1BC1 again at E ‰ B. Prove that the lines...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2013 Shortlist ›

IMO 2013 Shortlist G5

IMO 2013 Shortlist G5 Category: Geometry Problem Let ABCDEF be a convex hexagon with AB “ DE, BC “ EF, CD “ FA, and =A ´ =D “ =C ´ =F “ =E ´ =B. Prove that the diagonals AD,BE, and CF are concurrent. (Ukraine)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2017 Shortlist ›

IMO 2017 Shortlist G4

IMO 2017 Shortlist G4 Category: Geometry Problem In triangle ABC, let ω be the ex ir le opposite A. Let D, E, and F be the points where ω is tangent to lines BC, CA, and AB, respe tively. The ir le AEF interse ts line BC at P and Q. Let M be the midpoint of AD. Prove that the ir le MPQ is tangent to ω. (Denmark)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2021 Shortlist ›

IMO 2021 Shortlist G6

IMO 2021 Shortlist G6 Category: Geometry Problem Determine all integers n ě 3 satisfying the following property: every convex n-gon whose sides all have length 1 contains an equilateral triangle of side length 1. (Every polygon is assumed to contain its boundary.) Shortlisted problems 9

Practice › Mathematics › IMO › IMO Shortlist › IMO 2012 Shortlist ›

IMO 2012 Shortlist G8

IMO 2012 Shortlist G8 Category: Geometry Problem Let ABC be a triangle with circumcircle ω and ℓ a line without common points with ω. Denote by P the foot of the perpendicular from the center of ω to ℓ. The side-lines BC,CA,AB intersect ℓ at the points X,Y,Z different from P. Prove that the circumcircles of the triangles AXP,BY P and CZP have a common point different from P or...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2014 Shortlist ›

IMO 2014 Shortlist G6

IMO 2014 Shortlist G6 Category: Geometry Problem Let ABC be a fixed acute-angled triangle. Consider some points E and F lying on the sides AC and AB, respectively, and let M be the midpoint of EF. Let the perpendicular bisector of EF intersect the line BC at K, and let the perpendicular bisector of MK intersect the lines AC and AB at S and T, respectively. We call the pair...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2011 Shortlist ›

IMO 2011 Shortlist G1

IMO 2011 Shortlist G1 Category: Geometry Problem Let ABC be an acute triangle. Let ω be a circle whose center L lies on the side BC. Suppose that ω is tangent to AB at B′ and to AC at C′ . Suppose also that the circumcenter O of the triangle ABC lies on the shorter arc B′ C′ of ω. Prove that the circumcircle of ABC and ω meet at...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2008 Shortlist ›

IMO 2008 Shortlist G6

IMO 2008 Shortlist G6 Category: Geometry Problem There is given a convex quadrilateral ABCD. Prove that there exists a point P inside the quadrilateral such that ∠PAB + ∠PDC = ∠PBC + ∠PAD = ∠PCD + ∠PBA = ∠PDA + ∠PCB = 90◦ (1) if and only if the diagonals AC and BD are perpendicular.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2015 Shortlist ›

IMO 2015 Shortlist G8

IMO 2015 Shortlist G8 Category: Geometry Problem A triangulation of a convex polygon Π is a partitioning of Π into triangles by diagonals having no common points other than the vertices of the polygon. We say that a triangulation is a Thaiangulation if all triangles in it have the same area. Prove that any two different Thaiangulations of a convex polygon Π differ by exactly two triangles. (In other words,...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2007 Shortlist ›

IMO 2007 Shortlist G2

IMO 2007 Shortlist G2 Category: Geometry Problem Given an isosceles triangle ABC with AB = AC. The midpoint of side BC is denoted by M. Let X be a variable point on the shorter arc MA of the circumcircle of triangle ABM. Let T be the point in the angle domain BMA, for which ∠TMX = 90◦ and TX = BX. Prove that ∠MTB − ∠CTM does not depend on...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2023 Shortlist ›

IMO 2023 Shortlist G8

IMO 2023 Shortlist G8 Category: Geometry Problem Let ABC be an equilateral triangle. Points A1, B1, C1 lie inside triangle ABC such that triangle A1B1C1 is scalene, BA1 “ A1C, CB1 “ B1A, AC1 “ C1B and =BA1C =CB1A =AC1B “ 480˝ . Lines BC1 and CB1 intersect at A2; lines CA1 and AC1 intersect at B2; and lines AB1 and BA1 intersect at C2. Prove that the circumcircles of...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2018 Shortlist ›

IMO 2018 Shortlist G1

IMO 2018 Shortlist G1 Category: Geometry Problem Let ABC be an a ute-angled triangle with ir um ir le Γ. Let D and E be points on the segments AB and AC, respe tively, su h that AD “ AE. The perpendi ular bise tors of the segments BD and CE interse t the small ar s Ŋ AB and Ŋ AC at points F and G respe tively. Prove...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2006 Shortlist ›

IMO 2006 Shortlist G8

IMO 2006 Shortlist G8 Category: Geometry Problem Let ABCD be a convex quadrilateral. A circle passing through the points A and D and a circle passing through the points B and C are externally tangent at a point P inside the quadrilateral. Suppose that ∠PAB + ∠PDC ≤ 90◦ and ∠PBA + ∠PCD ≤ 90◦ . Prove that AB + CD ≥ BC + AD. (Poland)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2022 Shortlist ›

IMO 2022 Shortlist G6

IMO 2022 Shortlist G6 Category: Geometry Problem In an acute-angled triangle ABC, point H is the foot of the altitude from A. Let P be a moving point such that the bisectors k and of angles PBC and PCB, respectively, intersect each other on the line segment AH. Let k and AC meet at E, let and AB meet at F, and let EF and AH meet at Q. Prove...

Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

k-d Tree Search

k-d Tree Search k-d tree search organizes points in k-dimensional space using recursive axis aligned partitions. Each level splits the space along one coordinate axis. It supports both exact membership queries and range or nearest neighbor search. Problem Given a set of points in k-dimensional space and a query point or region, find: whether a point exists or all points in a region or the nearest neighbor Structure Each node...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2009 Shortlist ›

IMO 2009 Shortlist G5

IMO 2009 Shortlist G5 Category: Geometry Problem Let P be a polygon that is convex and symmetric to some point O. Prove that for some parallelogram R satisfying P ⊂ R we have |R| |P| ≤ √ where |R| and |P| denote the area of the sets R and P, respectively.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2019 Shortlist ›

IMO 2019 Shortlist G7

IMO 2019 Shortlist G7 Category: Geometry Problem The incircle ω of acute-angled scalene triangle ABC has centre I and meets sides BC, CA, and AB at D, E, and F, respectively. The line through D perpendicular to EF meets ω again at R. Line AR meets ω again at P. The circumcircles of triangles PCE and PBF meet again at Q ‰ P. Prove that lines DI and PQ meet...

Wiki › Algorithms › 02. Data Structures › 3. Specialized, Persistent, Concurrent, and External Structures ›

3.4 Geometric Data Structures

3.4 Geometric data structures, 40 index slug name 1 geometric-data-structure Geometric Data Structure 2 point-set Point Set 3 line-segment-set Line Segment Set 4 interval-tree-geometric Interval Tree 5 segment-tree-geometric Geometric Segment Tree 6 range-tree-geometric Range Tree 7 two-dimensional-range-tree-geometric 2D Range Tree 8 kd-tree KD Tree 9 kd-tree-nearest-neighbor KD Tree Nearest Neighbor 10 ball-tree Ball Tree 11 vp-tree Vantage Point Tree 12 cover-tree Cover Tree 13 quadtree Quadtree 14 octree Octree 15...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2019 Shortlist ›

IMO 2019 Shortlist G3

IMO 2019 Shortlist G3 Category: Geometry Problem In triangle ABC, let A1 and B1 be two points on sides BC and AC, and let P and Q be two points on segments AA1 and BB1, respectively, so that line PQ is parallel to AB. On ray PB1, beyond B1, let P1 be a point so that =PP1C “ =BAC. Similarly, on ray QA1, beyond A1, let Q1 be a point...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2015 Shortlist ›

IMO 2015 Shortlist G4

IMO 2015 Shortlist G4 Category: Geometry Problem Let ABC be an acute triangle, and let M be the midpoint of AC. A circle ω passing through B and M meets the sides AB and BC again at P and Q, respectively. Let T be the point such that the quadrilateral BPTQ is a parallelogram. Suppose that T lies on the circumcircle of the triangle ABC. Determine all possible values of...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2018 Shortlist ›

IMO 2018 Shortlist G2

IMO 2018 Shortlist G2 Category: Geometry Problem Let ABC be a triangle with AB “ AC, and let M be the midpoint of BC. Let P be a point su h that PB ă PC and PA is parallel to BC. Let X and Y be points on the lines PB and PC, respe tively, so that B lies on the segment PX, C lies on the segment PY ,...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2013 Shortlist ›

IMO 2013 Shortlist G1

IMO 2013 Shortlist G1 Category: Geometry Problem Let ABC be an acute-angled triangle with orthocenter H, and let W be a point on side BC. Denote by M and N the feet of the altitudes from B and C, respectively. Denote by ω1 the circumcircle of BWN, and let X be the point on ω1 which is diametrically opposite to W. Analogously, denote by ω2 the circumcircle of CWM, and...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2016 Shortlist ›

IMO 2016 Shortlist G5

IMO 2016 Shortlist G5 Category: Geometry Problem Let D be the foot of perpendicular from A to the Euler line (the line passing through the circumcentre and the orthocentre) of an acute scalene triangle ABC. A circle ω with centre S passes through A and D, and it intersects sides AB and AC at X and Y respectively. Let P be the foot of altitude from A to BC, and...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2023 Shortlist ›

IMO 2023 Shortlist G3

IMO 2023 Shortlist G3 Category: Geometry Problem Let ABCD be a cyclic quadrilateral with =BAD ă =ADC. Let M be the midpoint of the arc CD not containing A. Suppose there is a point P inside ABCD such that =ADB “ =CPD and =ADP “ =PCB. Prove that lines AD,PM,BC are concurrent. (Slovakia)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2023 Shortlist ›

IMO 2023 Shortlist G1

IMO 2023 Shortlist G1 Category: Geometry Problem Let ABCDE be a convex pentagon such that =ABC “ =AED “ 90˝ . Suppose that the midpoint of CD is the circumcentre of triangle ABE. Let O be the circumcentre of triangle ACD. Prove that line AO passes through the midpoint of segment BE. (Slovakia)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2020 Shortlist ›

IMO 2020 Shortlist G6

IMO 2020 Shortlist G6 Category: Geometry Problem Let I and IA be the incenter and the A-excenter of an acute-angled triangle ABC with AB ă AC. Let the incircle meet BC at D. The line AD meets BIA and CIA at E and F, respectively. Prove that the circumcircles of triangles AID and IAEF are tangent to each other. (Slovakia) Shortlisted problems 9

Practice › Mathematics › IMO › IMO Shortlist › IMO 2017 Shortlist ›

IMO 2017 Shortlist G6

IMO 2017 Shortlist G6 Category: Geometry Problem Let n ě 3 be an integer. Two regular n-gons A and B are given in the plane. Prove that the verti es of A that lie inside B or on its boundary are onse utive. (That is, prove that there exists a line separating those verti es of A that lie inside B or on its boundary from the other verti es...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2009 Shortlist ›

IMO 2009 Shortlist G2

IMO 2009 Shortlist G2 Category: Geometry Problem Let ABC be a triangle with circumcenter O. The points P and Q are interior points of the sides CA and AB, respectively. The circle k passes through the midpoints of the segments BP, CQ, and PQ. Prove that if the line PQ is tangent to circle k then OP = OQ.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2010 Shortlist ›

IMO 2010 Shortlist G3

IMO 2010 Shortlist G3 Category: Geometry Problem Let A1A2 ...An be a convex polygon. Point P inside this polygon is chosen so that its projections P1, ..., Pn onto lines A1A2, ..., AnA1 respectively lie on the sides of the polygon. Prove that for arbitrary points X1, ..., Xn on sides A1A2, ..., AnA1 respectively, max " X1X2 P1P2 ,..., XnX1 PnP1 * ©1. (Armenia)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2011 Shortlist ›

IMO 2011 Shortlist G4

IMO 2011 Shortlist G4 Category: Geometry Problem Let ABC be an acute triangle with circumcircle Ω. Let B0 be the midpoint of AC and let C0 be the midpoint of AB. Let D be the foot of the altitude from A, and let G be the centroid of the triangle ABC. Let ω be a circle through B0 and C0 that is tangent to the circle Ω at a point...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2024 Shortlist ›

IMO 2024 Shortlist G3

IMO 2024 Shortlist G3 Category: Geometry Problem Let ABCDE be a convex pentagon and let M be the midpoint of AB. Suppose that segment AB is tangent to the circumcircle of triangle CME at M and that D lies on the circumcircles of triangles AME and BMC. Lines AD and ME intersect at K, and lines BD and MC intersect at L. Points P and Q lie on line EC...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2009 Shortlist ›

IMO 2009 Shortlist G1

IMO 2009 Shortlist G1 Category: Geometry Problem Let ABC be a triangle with AB = AC. The angle bisectors of A and B meet the sides BC and AC in D and E, respectively. Let K be the incenter of triangle ADC. Suppose that ∠BEK = 45◦ . Find all possible values of ∠BAC.

Practice › Mathematics › IMO › IMO Shortlist › IMO 2013 Shortlist ›

IMO 2013 Shortlist G3

IMO 2013 Shortlist G3 Category: Geometry Problem In a triangle ABC, let D and E be the feet of the angle bisectors of angles A and B, respectively. A rhombus is inscribed into the quadrilateral AEDB (all vertices of the rhombus lie on different sides of AEDB). Let ϕ be the non-obtuse angle of the rhombus. Prove that ϕ ď maxt=BAC,=ABCu. (Serbia)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2015 Shortlist ›

IMO 2015 Shortlist G1

IMO 2015 Shortlist G1 Category: Geometry Problem Let ABC be an acute triangle with orthocenter H. Let G be the point such that the quadrilateral ABGH is a parallelogram. Let I be the point on the line GH such that AC bisects HI. Suppose that the line AC intersects the circumcircle of the triangle GCI at C and J. Prove that IJ “ AH. (Australia)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2021 Shortlist ›

IMO 2021 Shortlist G5

IMO 2021 Shortlist G5 Category: Geometry Problem Let ABCD be a cyclic quadrilateral whose sides have pairwise different lengths. Let O be the circumcentre of ABCD. The internal anglebisectors of =ABC and =ADC meet AC at B1 and D1, respectively. Let OB be the centre of the circle which passes through B and is tangent to AC at D1. Similarly,let OD be the centre of the circle which passes through...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2022 Shortlist ›

IMO 2022 Shortlist G1

IMO 2022 Shortlist G1 Category: Geometry Problem Let ABCDE be a convex pentagon such that BC “ DE. Assume there is a point T inside ABCDE with TB “ TD, TC “ TE and =TBA “ =AET. Let lines CD and CT intersect line AB at points P and Q, respectively, and let lines CD and DT intersect line AE at points R and S, respectively. Assume that points P,B,A,Q...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2016 Shortlist ›

IMO 2016 Shortlist G6

IMO 2016 Shortlist G6 Category: Geometry Problem Let ABCD be a convex quadrilateral with ∠ABC = ∠ADC < 90◦ . The internal angle bisectors of ∠ABC and ∠ADC meet AC at E and F respectively, and meet each other at point P. Let M be the midpoint of AC and let ω be the circumcircle of triangle BPD. Segments BM and DM intersect ω again at X and Y respectively....

Practice › Mathematics › IMO › IMO Shortlist › IMO 2024 Shortlist ›

IMO 2024 Shortlist G4

IMO 2024 Shortlist G4 Category: Geometry Problem Let ABCD be a quadrilateral with AB parallel to CD and AB ă CD. Lines AD and BC intersect at a point P. Point X ‰ C on the circumcircle of triangle ABC is such that PC “ PX. Point Y ‰ D on the circumcircle of triangle ABD is such that PD “ PY . Lines AX and BY intersect at Q....

Practice › Mathematics › IMO › IMO Shortlist › IMO 2022 Shortlist ›

IMO 2022 Shortlist G4

IMO 2022 Shortlist G4 Category: Geometry Problem Let ABC be an acute-angled triangle with AC ą AB, let O be its circumcentre, and let D be a point on the segment BC. The line through D perpendicular to BC intersects the lines AO, AC and AB at W, X and Y , respectively. The circumcircles of triangles AXY and ABC intersect again at Z ‰ A. Prove that if OW...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2013 Shortlist ›

IMO 2013 Shortlist G2

IMO 2013 Shortlist G2 Category: Geometry Problem Let ω be the circumcircle of a triangle ABC. Denote by M and N the midpoints of the sides AB and AC, respectively, and denote by T the midpoint of the arc BC of ω not containing A. The circumcircles of the triangles AMT and ANT intersect the perpendicular bisectors of AC and AB at points X and Y , respectively; assume that...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2015 Shortlist ›

IMO 2015 Shortlist G5

IMO 2015 Shortlist G5 Category: Geometry Problem Let ABC be a triangle with CA ‰ CB. Let D, F, and G be the midpoints of the sides AB, AC, and BC, respectively. A circle Γ passing through C and tangent to AB at D meets the segments AF and BG at H and I, respectively. The points H1 and I1 are symmetric to H and I about F and G,...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2011 Shortlist ›

IMO 2011 Shortlist G3

IMO 2011 Shortlist G3 Category: Geometry Problem Let ABCD be a convex quadrilateral whose sides AD and BC are not parallel. Suppose that the circles with diameters AB and CD meet at points E and F inside the quadrilateral. Let ωE be the circle through the feet of the perpendiculars from E to the lines AB, BC, and CD. Let ωF be the circle through the feet of the perpendiculars...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2011 Shortlist ›

IMO 2011 Shortlist G7

IMO 2011 Shortlist G7 Category: Geometry Problem Let ABCDEF be a convex hexagon all of whose sides are tangent to a circle ω with center O. Suppose that the circumcircle of triangle ACE is concentric with ω. Let J be the foot of the perpendicular from B to CD. Suppose that the perpendicular from B to DF intersects the line EO at a point K. Let L be the foot...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2013 Shortlist ›

IMO 2013 Shortlist G6

IMO 2013 Shortlist G6 Category: Geometry Problem Let the excircle of the triangle ABC lying opposite to A touch its side BC at the point A1. Define the points B1 and C1 analogously. Suppose that the circumcentre of the triangle A1B1C1 lies on the circumcircle of the triangle ABC. Prove that the triangle ABC is right-angled. (Russia) Shortlisted problems 7

Practice › Mathematics › IMO › IMO Shortlist › IMO 2024 Shortlist ›

IMO 2024 Shortlist G7

IMO 2024 Shortlist G7 Category: Geometry Problem Let ABC be a triangle with incentre I such that AB ă AC ă BC. The second intersections of AI, BI, and CI with the circumcircle of triangle ABC are MA, MB, and MC, respectively. Lines AI and BC intersect at D and lines BMC and CMB intersect at X. Suppose the circumcircles of triangles XMBMC and XBC intersect again at S ‰...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2021 Shortlist ›

IMO 2021 Shortlist G7

IMO 2021 Shortlist G7 Category: Geometry Problem A point D is chosen inside an acute-angled triangle ABC with AB ą AC so that =BAD “ =DAC. A point E is constructed on the segment AC so that =ADE “ =DCB. Similarly, a point F is constructed on the segment AB so that =ADF “ =DBC. A point X is chosen on the line AC so that CX “ BX. Let...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2016 Shortlist ›

IMO 2016 Shortlist G2

IMO 2016 Shortlist G2 Category: Geometry Problem Let ABC be a triangle with circumcircle Γ and incentre I. Let M be the midpoint of side BC. Denote by D the foot of perpendicular from I to side BC. The line through I per- pendicular to AI meets sides AB and AC at F and E respectively. Suppose the circumcircle of triangle AEF intersects Γ at a point X other than...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2014 Shortlist ›

IMO 2014 Shortlist G3

IMO 2014 Shortlist G3 Category: Geometry Problem Let Ω and O be the circumcircle and the circumcentre of an acute-angled triangle ABC with AB ą BC. The angle bisector of =ABC intersects Ω at M ‰ B. Let Γ be the circle with diameter BM. The angle bisectors of =AOB and =BOC intersect Γ at points P and Q, respectively. The point R is chosen on the line PQ so...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2020 Shortlist ›

IMO 2020 Shortlist G9

IMO 2020 Shortlist G9 Category: Geometry Problem Prove that there exists a positive constant c such that the following statement is true: Assume that n is an integer with n ě 2, and let S be a set of n points in the plane such that the distance between any two distinct points in S is at least 1. Then there is a line ℓ separating S such that the...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2020 Shortlist ›

IMO 2020 Shortlist G2

IMO 2020 Shortlist G2 Category: Geometry Problem Let ABCD be a convex quadrilateral. Suppose that P is a point in the interior of ABCD such that =PAD : =PBA : =DPA “ 1 : 2 : 3 “ =CBP : =BAP : =BPC. The internal bisectors of angles ADP and PCB meet at a point Q inside the triangle ABP. Prove that AQ “ BQ. (Poland)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2012 Shortlist ›

IMO 2012 Shortlist G1

IMO 2012 Shortlist G1 Category: Geometry Problem In the triangle ABC the point J is the center of the excircle opposite to A. This excircle is tangent to the side BC at M, and to the lines AB and AC at K and L respectively. The lines LM and BJ meet at F, and the lines KM and CJ meet at G. Let S be the point of intersection of...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2018 Shortlist ›

IMO 2018 Shortlist G3

IMO 2018 Shortlist G3 Category: Geometry Problem A ir le ω of radius 1 is given. A olle tion T of triangles is alled good, if the following onditions hold: piq ea h triangle from T is ins ribed in ω; piiq no two triangles from T have a ommon interior point. Determine all positive real numbers t su h that, for ea h positive integer n, there exists a...

Practice › Mathematics › IMO › IMO Shortlist › IMO 2007 Shortlist ›

IMO 2007 Shortlist G3

IMO 2007 Shortlist G3 Category: Geometry Problem The diagonals of a trapezoid ABCD intersect at point P. Point Q lies between the parallel lines BC and AD such that ∠AQD = ∠CQB, and line CD separates points P and Q. Prove that ∠BQP = ∠DAQ. (Ukraine)

Practice › Mathematics › IMO › IMO Shortlist › IMO 2011 Shortlist ›

IMO 2011 Shortlist G5

IMO 2011 Shortlist G5 Category: Geometry Problem Let ABC be a triangle with incenter I and circumcircle ω. Let D and E be the second intersection points of ω with the lines AI and BI, respectively. The chord DE meets AC at a point F, and BC at a point G. Let P be the intersection point of the line through F parallel to AD and the line through G...

#geometry

17.11 Rectangle Union Area

17.12 Half-Plane Intersection

17.2 Orientation Tests

17.22 Correctness Proofs

17.23 Testing Geometry Algorithms

17.3 Line and Segment Intersection

17.14 Delaunay Triangulation Overview

17.25 Case Studies

17.9 Sweep Line Algorithms

17.5 Point in Polygon

17.10 Interval Geometry

Chapter 17. Computational Geometry

17.8 Closest Pair of Points

17.18 Geometric Hashing

17.24 Performance Optimization

17.21 Geometry Design Patterns

17.7 Rotating Calipers

17.1 Points and Vectors

17.17 Floating-Point Robustness

17.6 Convex Hull

17.4 Polygon Area

17.13 Voronoi Diagrams Overview

17.16 Integer Geometry

17.19 Spatial Indexes

17.15 Precision Errors

17.20 Geometry Libraries and Practical Patterns

CF 2225E - Covering Points with Circles

CF 1952I - Dark Matter

CF 1942C1 - Bessie's Birthday Cake (Easy Version)

CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)

CF 1949A - Grove

European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)

CF 1942C2 - Bessie's Birthday Cake (Hard Version)

LeetCode 3464 - Maximize the Distance Between Points on a Square

LeetCode 3625 - Count Number of Trapezoids II

LeetCode 3588 - Find Maximum Area of a Triangle

CF 460E - Roland and Rose

CF 464B - Restore Cube

Codeforces Round 265 (Div. 1)

MemSQL Start[c]UP 2.0 - Round 1

CF 452B - 4-point polyline

Codeforces Round 271 (Div. 2)

CF 474C - Captain Marmot

LeetCode 3025 - Find the Number of Ways to Place People I

IMO 2000 SL G4

IMO 2001 SL G8

IMO 2000 SL G7

IMO 1999 SL G5

IMO 1999 SL G6

IMO 1996 SL G8

IMO 2003 SL G5

IMO 1995 SL G5

IMO 1994 SL G5

IMO 1996 SL G1

IMO 1995 SL G8

IMO 1996 SL G5

IMO 2000 SL G2

IMO 2003 SL G7

IMO 2002 SL G3

IMO 2000 SL G3

IMO 2001 SL G3

IMO 2002 SL G2

IMO 1994 SL G3

IMO 2003 SL G1

IMO 1999 SL G4

IMO 1995 SL G3

IMO 1994 SL G2

IMO 2003 SL G6

IMO 2001 SL G5

IMO 1996 SL G9

IMO 2000 SL G1

IMO 1995 SL G2

IMO 2003 SL G2

IMO 1995 SL G1

IMO 2004 SL G7

IMO 1995 SL G6

IMO 2002 SL G1

IMO 2002 SL G6

IMO 1996 SL G2