This is an interesting problem which I was not able to solve by the first try and I will shortly explain why after I explain what is my solution ( O(N) time where N is the maximum Y value).

We get the information about the two lines which make the triangle. By information, I mean the slope and the C value. (y = slope*x + C).

The we just iterate from 0 to the maximum Y value of our triangle (the pivot point) and we check what is the possible leftest value and accordingly rightest value. Then we add the value count (right-left+1) to our COUNT variable.

Everything seems fine and the solution yields just O(N) time where N is at maximum 32 000 (a fairly small number).

You may as well try the solution on your really cool computer with the latest 64bit processor and you will probably always get the right answer. But after you submit it, you will get a wrong answer warning from USACO. How come? Everything works correct on your computer? Well, it is mostly because your processor is 64bit and their maybe 32bit? I don’t really know and I do not want to get into really technical stuff.

The problem is with the decimal part. For example, we may receive for rights X value 9.999998 which should be actually 10.0 or it might be even 10.01 or even more. We will add an EPS value (a very small number) to check whether one value equals another. For example, 9.99998 will equal 10.00 and 10.0001 will equal 10.00.

Just now our program seems to work flawlessly.

#include <iostream> #include <string> #include <fstream> #include <vector> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <set> #include <cstring> using namespace std; #define INF -99999.0 #define EPS 0.00001 double n,m,p; long long cnt = 0; struct line { double k; double c; }; line leftLine,rightLine; line makeLine (double k, double c) { line tmp; tmp.k = k; tmp.c = c; return tmp; } double slope(double x1, double y1, double x2, double y2) { if (x2-x1==0.0) return INF; return (y2-y1)/(x2-x1); } double properRound(double value) { double ceiled = ceil(value); double floored = floor(value); if (value-EPS <= floored) return floored; if (value+EPS >= ceiled) return ceiled; return value; } int getLeft(int y) { if (leftLine.k == INF) { return 1; } double pos = properRound((y-leftLine.c)/leftLine.k); return floor(pos + 1.0); } int getRight(int y) { double pos = properRound((y-rightLine.c)/rightLine.k); return ceil(pos-1.0); } int getCount(int y) { return getRight(y)-getLeft(y)+1; } void solve() { leftLine = makeLine(slope(0.0,0.0,n,m),0.0); rightLine = makeLine(slope(p,0.0,n,m),-slope(p,0.0,n,m)*p); for (double i = 1.0; i < m; i+=1.0) { cnt += getCount(i); } } int main() { ifstream in("fence9.in"); in >> n >> m >> p; in.close(); solve(); ofstream out("fence9.out"); out << cnt << endl; out.close(); return 0; }