The minimum value attained over all straight line equations Suppose I have $1000$ straight line equations of the form $y = mx + c$. Now for every straight line we know the value of $m$ and $c$. We are also given a value of $x$. After putting the value of x in all the straight lines, we need to select the output($y$ value) which is the minimal.
My question is, Is there any better way to do this by just seeing the equations? I don't want to substitute x values in all equations and then check.
 A: Following the comment of cyanide, you can sort the lines according the their values of $m,c$. You may be able to rule out many of the lines by doing this. For example, if $x>0$, and both $m_1>m_2$ and $c_1>c_2$ we know that $m_1x+c_1>m_2x+c_2$.
However, if for example $m_1>m_2$ but $c_1<c_2$ then it's a bit more complicated. 
Consider $y_1 = m_1x+c_1$ and $y_2 = m_2x+c_2$. Let's find the values of $x>0$ such that $y_1>y_2$.
$$m_1+c_1>m_2x+c_2 \implies x> \frac{c_2-c_1}{m_1-m_2}.$$
Doing this enables you to sort the lines into partitions where they are the greatest on particular intervals of $x$.
Edit: A simpler way is to find the intersection of the 2 lines which is at 
$$x_p = \frac{c_2-c_1}{m_1-m_2}$$
then you know the line with the larger gradient is going to be larger for $x>x_p$ and less for $x<x_p$. 
A: No, in general there is no way to rule out significant subset of lines in each possible case.
Imagine a concave function, say $y=-x^2$, and draw a thousand lines tangent to its graph. For each of those lines there exists a range of $x$ (a neighborhood of that line's tangency point's abscissa) in which that line gives a minimum $y$.

You can't rule out any one line from the set....
UPDATE
This seems algorithmic problem rather than mathematical one.
Start with a single scan through all lines and find those with the largest and the smallest $m$. They will be the first (leftmost) and last (rightmost) segments of the polygonal chain defining your 'minimum $y$ for given $x$' function (as Dan Uznanski explains in the answer).
If you find repeated values of $m$, choose the line with smaller $c$ and remove those with bigger $c$ from further analysis. The lines with equal $m$ are parallel, and those with bigger $c$ lie above those with smaller $c$, hence they'll never take part in the final solution.
Find the intersection of the two lines found and you have a partial solution: a single vertex of the chain with two slopes $m$, one to the left and the other to the right from the vertex point.
Next you extend the solution line by line.

Iterate adding the remaining lines. For each line not considered yet test the vertices and find those above the new line. If none is above, discard the line. Otherwise, all vertices above the line get removed from the chain. Instead two new vertices are added.

If there exist some unremoved vertices at either side of the removed group, find an intersection of the new line with the corresponding segment and shorten the segment appropriately, otherwise find an intersection with the leftmost or rightmost line, respective to the side.
If the intersection happens at the vertex, just remove the whole segment and keep the vertex.

That is $N-2$ steps of adding a line. In each step you scan up to $N-2$ vertices, modify $2$ segments, add $1$ segment and remove up to $N-2$ segments.
The cost of the last operation strongly depends on a data structure you use to keep the resulting chain. If you keep nodes in a self-balancing binary search tree (BST), it would make the cost of single vertex addition or removal $O(\log N)$.
As a result the pessimistic total cost is $O(N\cdot(N+N\log N)) = O(N^2\log N)$ elementary operations (some of them being calculating $mx+c$ to determine whether a vertex is above a line, some being elementary modifications in the binary tree structure).
However, if we consider you can not remove more vertices than you previously added, and in each step you add at most $2$ vertices, the total number of additions and removals can't exceed or even reach $2N$, hence the cost is $O(N\cdot N + N) = O(N^2)$.
Can we reduce it any further?
If you keep vertices ordered by $x$, e.g. in a BST, you can find vertices to remove in logarithmic time. The crucial observation you should make is the chain forms a convex curve, hence the vertices to remove (if any) make a contiguous block. So we can use a divide-and-conquer method to search the first and last vertex to remove.
Compare the new line to the midle vertex first. If the vertex is above the line continue searching the leftmost vertex to delete in the left half of the set, and the rightmost vertex in the right half of the set. Each time you shrink the area by half, hence you make $O(\log N)$ comparisions on each side.
If, OTOH, the first vertex is below the line, compare the slopes of the left and right segment to the slope of the line.

If the left segment's slope is greater, and the right segment's slope is smaller than a slope of the new line, there certainly can be no more candidate and the line gets discarded. You're done with that step. Otherwise you can easily determine appropriate half, where some vertex above the line can possily be found; then proceed with that half. As before, that requires $O(\log N)$ comparisions.
As a result, you need $O(N\cdot\log N)$ operations to find a final chain.
Then each input point can be examined against the chain in $O(\log N)$ steps, again thanks to binary search in vertices' $x$ values.
A: 1: sort the lines in descending order based on $m$.  You know that the first item on this list is smallest at $x=-\infty$, and the last is smallest at $x=\infty$.  It's the stuff in between we're concerned about now; we will use this sorted structure to continue.  We'll call the current line $f$, and start with $f$ as the first line.
2: Find, using $x=\frac{c_g-c_f}{m_f-m_g}$ for each item $g$ in the list after $f$, the smallest $x$ where a line crosses $f$, and the corresponding line $g$. (In the case of ties, use the last line that matches) Now, we know that $f$ has the minimal value of all lines from the previous $x$ to the new $x$.  Repeat this process, using the current $g$ as the new $f$, until you have exhausted the whole list.
Now, you have a list of lines and the intervals on which they are minimal; any line you've managed to never call $f$ and assigned an interval to are never minimal and can be discarded.  Using a binary search you are now never more than 10 or so direct comparisons away from finding the correct line.
The result is an $O(n^2)$ setup process that turns later checks from $O(n)$ to $O(\log n)$; this becomes much more efficient if you expect a single pile of lines to be checked a large number of times.
