USACO 3.4.3 Electric Fence 解题报告

题目本质：相似三角形+枚举 算法描述：题目给出的三角形比较特殊，所以可以直接枚举，当然也不能说是直接枚举咯。我的算法是，对于每一行进行枚举，但是很快就到瓶颈了，无法确定坐标，虽然能够画出相似三角形，因为三角形的一条边在x轴上，所以从y等于(-)1（看情况而定是1还是-1）至m，每一行做与x轴平行的线就有相似三角形了，但是只能确定长短，不能确定坐标，后来想了好阵子，才想到，用高来确定坐标，用两个三角形，(n, m)(n, 0)(0, 0)，(m, n)(n, 0)(p, 0)，分别可以把新坐标求出来，然后一个向上取整，一个向下取整，相减+1就可以了，接下来就是细节了。 Pay attention：y=0 不计算，x轴上所有的点都在线上，不符合要求；如果在某个y上，x1, x2(相似三角形求出的两个坐标), x1, x2为整数的话, 那么x1, x2连点都不能取。 复 杂 度：这题不会分析，不知道什么是N。 de lang="c">/ LANG: C ID: yylogoo1 PROG: fence9 / #include #include #include $\#define\; swap(a,\; b)\; do\{\backslash \; int\; t;\backslash \; t\; =\; a;\backslash \; a\; =\; b;\backslash \; b\; =\; t;\backslash \; \}while(0)\; int\; main(int\; argc,\; char$argv[]) { int i; int x[2] = {0}; int a, b, k; int x1, x2; double t; int ans = 0; freopen("fence9.in", "r", stdin); freopen("fence9.out", "w", stdout); scanf("%d%d%d", &a, &b, &x[1]); if(x[0] < x[1]){ swap(x[0], x[1]); } k = b / abs(b); for(i = 1; i != b; i += k){ //向上取整 x1 = ceil(1.0 (b – i) / b (x[0] – a) + a); //自动向下取整 x2 = floor(1.0 (b – i) / b (x[1] – a) + a); ans += x2 – x1 + 1; t = 1.0 (b – i) / b (x[0] – a) + a; if(t <0 x t>= x1 – 0.00001){ ans–; } t = 1.0 (b – i) / b * (x[1] – a) + a; if(t <0 x t>= x1 – 0.00002){ ans–; } } printf("%d\n", ans); return 0; } de>