# SAMPLE INPUT
# 4
# 1 0
# 0 1
# -1 0
# 0 -1
fin = open ('moop.in', 'r')
fout = open ('moop.out', 'w')
# N = particles
N = int(fin.readline().strip())
print("N",N)
moo = [] # EACH PARTICLE HAS A DISTINCT SPIN
for i in range(N):
x,y = map(int,fin.readline().split())
moo.append((x,y))
moo.sort(reverse=True)
print(moo)
My first attempt at solving this problem was to search for the "dominant" points that can interact with (and possibly disappear) all points that are below and to the left on an XY plot. This is called the Pareto Frontier. The following Wikipedia article has more details on this concept.
# Find the Pareto Frontier, the points that are not dominated by any other points
# i.e. no points above or to the right
a,b = moo[0]
# the first point has largest X, so it is on the frontier
frontier = [(a,b)]
for x,y in moo[1:]:
if x<=a and y<=b:
continue
else:
frontier.append((x,y))
a=x
b=y
print(frontier)
There are two particles on the Pareto Frontier. The particles on the frontier can interact with and disappear any particles that have <=X and <=Y values (the frontier particles "dominate" these subordinate particles).
Unfortunately, the number of particles on the frontier is not the minumum possible remaining particles. The correct answer for this data set is 1. These two frontier particles cannot interact with each other, but they are connected through a shared subordinate particle. The subordinate particle could interact with both these particles and disappear them, leaving only the subordinate particle.
The correct answer is the number of "connected components" that exist within the Pareto particles. Version 2 of this code will check for shared subordinate particles among the Pareto particles.
