FZU 2127 养鸡场 线性规划？

 

设 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 long  
  
using 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;  
}  

 

 

补充：软件开发 , C++ ,