FZU 2127 养鸡场 线性规划？
题目链接：http://acm.fzu.edu.cn/problem.php?pid=2127
由题意知，a1+a2+a3 = n && a1 <= a2 <= a3.
设 a3 = tn ∈[x3, y3 > (n-1)/2 ? (n-1)/2 : a3 ],则对于每一个确定的tn，都有a1+a2 = n-tn.
又因为取值都为整数，所以问题转化为直线a1+a2 = n - tn 在某一区域内整点坐标的个数。
好啦，接下来就是要确定这个可行域的范围了。
设横坐标轴表示a1，纵坐标轴为表示a2。
其实可行域的范围为 三个范围的交集。
1 : 即题目中给出的 [x1,y1]和[x2,y2]的矩形范围。
2 : 因为a1<=a2<=a3,所以第二个范围为点(tn,tn)的左下方，包括(tn,tn)。
3 : 同样是因为a1 <= a2 ，所以第三个范围为( tn/2,tn/2 )的左上方，包括(tn/2,tn/2);
当然交集有可能为空。
由于最近在做计算几何，所以就习惯性的用计算几何的那一套来做了，然后又因为学艺不精被精度问题卡到死。。。。。。
不过FZU还是不错的吗，中文题好多哇。
#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <queue>#include <cmath>#include <algorithm>#define LL long longusing namespace std;struct R{ int Min,Max;} r[5];struct P{ double x,y;} p[6],l1,l2,cp[2];double CrossProduct(P a1,P a2,P b1,P b2){ P p1 = {a2.x-a1.x,a2.y-a1.y},p2 = {b2.x-b1.x,b2.y-b1.y}; return (p1.x*p2.y - p1.y*p2.x);}bool JudgeDotInLine(P a1,P a2,P b1){ if( sqrt((b1.x-a1.x)*(b1.x-a1.x) + (b1.y-a1.y)*(b1.y-a1.y))+sqrt((b1.x-a2.x)*(b1.x-a2.x) + (b1.y-a2.y)*(b1.y-a2.y)) - sqrt((a2.x-a1.x)*(a2.x-a1.x) + (a2.y-a1.y)*(a2.y-a1.y)) < (10e-8)) return true; return false;}bool JudgeCross(P a1,P a2,P b1,P b2){ double t1 = CrossProduct(a1,a2,a1,b2) * CrossProduct(a1,a2,a1,b1),t2 = CrossProduct(b1,b2,b1,a1)*CrossProduct(b1,b2,b1,a2); if(t1 < 0 && t2 < 0) return true; if(t1 == 0 && (JudgeDotInLine(a1,a2,b1) || JudgeDotInLine(a1,a2,b2) )) { return true; } if(t2 == 0 && (JudgeDotInLine(b1,b2,a1) || JudgeDotInLine(b1,b2,a2) )) { return true; } return false;}int main(){ int a3,i,n,sum,tn,top,mark; while(scanf("%d",&n) != EOF) { sum = 0; for(i = 1; i <= 3; ++i) { scanf("%d %d",&r[i].Min,&r[i].Max); } r[3].Max = r[3].Max > ((n-1)/2) ? ((n-1)/2) : r[3].Max; a3 = r[3].Min; while(a3 <= r[3].Max) { if(a3 < r[2].Min || a3 < r[1].Min || a3*3 < n) { a3++; continue; } p[1].x = r[1].Min; p[1].y = r[2].Min; p[2].x = r[1].Min; p[2].y = r[2].Max; p[3].x = r[1].Max; p[3].y = r[2].Max; p[4].x = r[1].Max; p[4].y = r[2].Min; mark = false; tn = n-a3; l1.x = 0; l1.y = tn; l2.x = tn; l2.y = 0; if(a3 < (tn+1)/2 || a3 < r[1].Min || a3 < r[2].Min || (tn+1)/2 > r[2].Max || (tn+1)/2 < r[1].Min) { a3++; continue; } p[2].y = (a3 < r[2].Max ? a3 : r[2].Max); p[3].y = (a3 < r[2].Max ? a3 : r[2].Max); p[1].y = ((tn+1)/2 > r[2].Min ? (tn+1)/2 : r[2].Min); p[4].y = ((tn+1)/2 > r[2].Min ? (tn+1)/2 : r[2].Min); p[3].x = ((tn+1)/2 < r[1].Max ? (tn+1)/2 : r[1].Max); p[4].x = ((tn+1)/2 < r[1].Max ? (tn+1)/2 : r[1].Max); p[3].x = (a3 < p[3].x ? a3 : p[3].x); p[4].x = (a3 < p[3].x ? a3 : p[4].x); top = 1; if(JudgeCross(p[2],p[3],l1,l2)) { mark = true; cp[top].y = p[2].y; cp[top++].x = tn - p[2].y; } else if(JudgeCross(p[1],p[2],l1,l2)) { mark = true; cp[top].x = p[2].x; cp[top++].y = tn - p[2].x; } if(JudgeCross(p[3],p[4],l1,l2)) { mark = true; cp[top].x = p[3].x; cp[top++].y = tn - p[3].x; } else if(JudgeCross(p[4],p[1],l1,l2)) { mark = true; cp[top].y = p[4].y; cp[top++].x = tn - p[4].y; } if(mark) { sum += (int)(cp[1].y-cp[2].y+1); } a3++; } cout<<sum<<endl; } return 0;}