#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <vector>
#include <climits>

class Point {
public:	
	Point(double _x, double _y) 
	{
		x = _x;
		y = _y;	
	}	
	double x, y;	
};

class Line {
public:	
	Line(){}
	Line(int _id, double _m, double _b) 
	{
		id = _id;
		m = _m;
		b = _b;
	}

	Point intersect(Line line)
	{
		double x = (((line.b - b) / (m - line.m)));
		double y = (m * x + b);
		return Point(x, y);
	}


	double m, b;
	double fromX = LONG_MIN;
	double toX = LONG_MAX;
	int id;
	bool visible = true;
};


void MergeSort(Line* _array, int h1, int h2);

int main(int argc, char *argv[])
{
	std::string inputFilename = argv[1];
	std::string outputFilename = argv[2];
	std::ifstream file(inputFilename.c_str());
	Line* lineList = new Line[100000];
	if (!file.good())
		return 1;
	std::string line = "";
	int size = 0;
	while (std::getline(file, line)) {
		int delim1 = line.find(',');
		int delim2 = line.find(',', delim1 + 1);
		int id = std::atoi(line.substr(0, delim1).c_str());
		double m = std::atof(line.substr(delim1 + 1, delim2).c_str());
		double b = std::atof(line.substr(delim2 + 1, line.size()).c_str());			
		lineList[size++] = Line(id, m, b);		
	}
	file.close();
	MergeSort(lineList, 0, size - 1);
	
	std::ofstream ofs(outputFilename, std::ofstream::out);

	for (int i = 0; i < size; ++i) 
		if(lineList[i].visible)
			ofs << lineList[i].id << "\n";	

	ofs.close();
	delete[] lineList;
	return 0;
}

void MergeSort(Line* _array, int h1, int h2)
{
	if (h1 >= h2) return;

	int midpoint = h1+(h2-h1)/2;
	MergeSort(_array, h1, midpoint);
	MergeSort(_array, midpoint + 1, h2);

	int h1_index = 0, h2_index = 0;
	int h1_end = midpoint - h1 + 1;
	int h2_end = h2 - midpoint;

	Line* left = new Line[h1_end];
	Line* right = new Line[h2_end];

	while(h1_index < h1_end) 
	{ 
		left[h1_index] = _array[h1 + h1_index];
		h1_index++;	
	}	
	
	while(h2_index < h2_end) 
	{
		right[h2_index] = _array[midpoint + 1 + h2_index];
		h2_index++;
	}

	h1_index = 0; 
    h2_index = 0; 
    int index = h1; 
	
	while (h1_index < h1_end && h2_index < h2_end) 
	{	
		
		Point isect = left[h1_index].intersect(right[h2_index]);		
		if (left[h1_index].m > right[h2_index].m) 
		{	
			if(left[h1_index].fromX < isect.x) 
				left[h1_index].fromX = isect.x;	
			if(right[h2_index].toX > isect.x) 
				right[h2_index].toX = isect.x;										
		}		
		else 
		{
			if(left[h1_index].toX > isect.x) 
				left[h1_index].toX = isect.x;				
			if(right[h2_index].fromX < isect.x) 
				right[h2_index].fromX = isect.x;			
		}

		if(left[h1_index].fromX < right[h2_index].fromX && 
		left[h1_index].toX >= right[h2_index].toX) {
			right[h2_index].visible = false;
		} else if(right[h2_index].fromX < left[h1_index].fromX && 
		right[h2_index].toX >= left[h1_index].toX) {
			left[h1_index].visible = false;
		}
	
		if(!left[h1_index].visible)
			_array[index++] = left[h1_index++];
		else if(!right[h2_index].visible)
			_array[index++] = right[h2_index++];	
		else if(left[h1_index].m < right[h2_index].m)
			_array[index++] = left[h1_index++];	
		else
			_array[index++] = right[h2_index++];		
	}	

	while (h1_index < h1_end) 
        	_array[index++] = left[h1_index++]; 

   	while (h2_index < h2_end)   
        	_array[index++] = right[h2_index++]; 

	delete[] left;
	delete[] right;
}