618C - Constellation - CodeForces Solution

import sys
from functools import cmp_to_key

input = sys.stdin.read
INF = float('inf')

class Point:
    def __init__(self, x=0, y=0, id=0):
        self.x = x
        self.y = y
        self.id = id

    def __lt__(self, other):
        if self.x != other.x:
            return self.x < other.x
        return self.y < other.y

def check(p1, p2, p3):
    x1, y1 = p1.x, p1.y
    x2, y2 = p2.x, p2.y
    x3, y3 = p3.x, p3.y

    if (x1 == x2 and x1 == x3) or (y1 == y2 and y1 == y3):
        return False
    return (y1 - y2) * (x1 - x3) != (y1 - y3) * (x1 - x2)

def solve():
    input_data = input().split()
    n = int(input_data[0])
    points = []
    index = 1
    for i in range(1, n + 1):
        x = int(input_data[index])
        y = int(input_data[index + 1])
        points.append(Point(x, y, i))
        index += 2
    
    points.sort()

    for i in range(n - 2):
        if check(points[i], points[i + 1], points[i + 2]):
            print(points[i].id, points[i + 1].id, points[i + 2].id)
            return

def main():
    solve()

if __name__ == "__main__":
    main()