## Waterloo 2023 Fall B - Orb Tent

View as PDF

Points: 17
Time limit: 10.0s
Memory limit: 256M

Problem types

You have found a collection of floating orbs of light, some of which are nice to look at, and some of which hurt to look at. We model this by each orb having a beauty value which is an arbitrary (possibly negative) integer. We want to build a tent which will house some subset of the orbs, and want the sum of the beauty of the orbs in the tent to be as large as possible. However, the tent must be convex.

Specifically, the position of each orb is at coordinates , where and , and the tent must be a convex polygon that includes the points and . Find the maximum sum of beauty of orbs inside any valid tent configuration.

An orb is considered inside the tent if it is exactly on the tent wall. The tent is considered convex even if some orb is exactly on a straight section of the tent wall (i.e. the angle of the tent wall at that orb is exactly degrees). It is allowed for the tent to not contain any of the orbs (i.e. and just lie on the ground).

#### Input Specification

The first line of input contains two integers and .

lines of input follow containing three integers each: the and coordinates of an orb and the beauty value of that orb.

#### Output Specification

Output a line containing a single integer, the maximum sum of beauty of orbs inside any valid tent configuration.

#### Sample Input 1

10 8
2 7 -1
2 5 2
3 5 1
4 5 -10
6 5 4
6 2 -1
7 2 2
7 3 -1
4 3 3
1 3 1

#### Sample Output 1

9

• commented on Oct. 11, 2023, 5:34 a.m.

What is a "tent wall"? I presume it means an edge of the convex polygon we are building?

The tent is considered convex even if some orb is exactly on a straight section of the tent wall (i.e. the angle of the tent wall at that orb is exactly 180 degrees).

How is whether an orb is on a tent wall even related to the convexity of the tent? In fact, what is even "the angle of the tent wall at the orb"? Angle between wall and what?

• commented on Oct. 12, 2023, 5:30 a.m.

What is a "tent wall"? I presume it means an edge of the convex polygon we are building?

Yes

How is whether an orb is on a tent wall even related to the convexity of the tent? In fact, what is even "the angle of the tent wall at the orb"? Angle between wall and what?

I think it's possible that someone might misinterpret an orb being directly along the tent wall as forcing it to "bulge out" or something similar (which could make the shape no longer convex). I think all it means is that if an orb is along the tent wall, we should still include it in the sum. Indeed, I ignored this note during the contest and it was fine.

• commented on Oct. 5, 2023, 11:34 p.m.

The positions of the orbs don't have to be distinct.