摘要: 之前做过CAD开发，对向量运算还是挺了解的，不过这题的边界情况害我wa了好多次。Q1：求线段是否相交，两两枚举，注意重复，可以考虑跨立实验，需要改进的话，可以在跨立实验前加快速排斥实验。Q2：设观察点为O，取线段AB，及AB中点C，连结AO、BO、CO；1. 枚举所有线段，若AO、BO与同一条线段相交，则AB看不到。2. 若A、B很近，则AB可以看成质点，AB看不到。3. 枚举所有线段，分别与AO...  阅读全文

一.矢量基本知识
    因为后面的计算需要一些矢量的基本知识，这里只是简单的列举如下，如果需要更加详细的信息，可以自行搜索wikipedia或google。
1.矢量的概念：如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。
2.矢量加减法：设二维矢量P = ( x1, y1 )，Q = ( x2 , y2 )，则矢量加法定义为： P + Q = ( x1 + x2 , y1 + y2 )，同样的，矢量减法定义为： P - Q = ( x1 - x2 , y1 - y2 )。显然有性质 P + Q = Q + P，P - Q = - ( Q - P )。
3.矢量的叉积：计算矢量叉积是与直线和线段相关算法的核心部分。设矢量P = ( x1, y1 )，Q = ( x2, y2 )，则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积，即：P × Q = x1*y2 - x2*y1，其结果是一个标量。显然有性质 P × Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。一般在不加说明的情况下，本文下述算法中所有的点都看作矢量，两点的加减法就是矢量相加减，而点的乘法则看作矢量叉积。
叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系：
　　若 P × Q > 0 , 则P在Q的顺时针方向。
　　若 P × Q < 0 , 则P在Q的逆时针方向。
　　若 P × Q = 0 , 则P与Q共线，但可能同向也可能反向。
4.折线段的拐向判断：折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2，通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向：
　　若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。
　　若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。
　　若(p2 - p0) × (p1 - p0) = 0,则p0、p1、p2三点共线。
这一条判断也可用来判断点在线段或直线的哪一测。

为了后文的叙述方便，先定义几个结构：

 

计算两条直线的叉积(cross production), 这里由于定义的都是二维的情况，本质上说，在平面上两个向量的叉积应该是垂直平面的，这里函数返回的整数值即为z轴上的值：

int crossProduct(v* v1, v* v2){ 
     v vt1, vt2; 
    int result = 0; 
     
     vt1.start.x = 0; 
     vt1.start.y = 0; 
     vt1.end.x = v1->end.x - v1->start.x; 
     vt1.end.y = v1->end.y - v1->start.y; 
     
     vt2.start.x = 0; 
     vt2.start.y = 0; 
     vt2.end.x = v2->end.x - v2->start.x; 
     vt2.end.y = v2->end.y - v2->start.y; 
     
     result = vt1.end.x * vt2.end.y - vt2.end.x * vt1.end.y; 
    return result; 
} 

二.判断两条直线相交
    先来看一个简单的情况，即判断两条直线是否相交。
第一个可能会想到的办法，就是判断斜率，这个在中学时代就学过了，不过斜率需要考虑垂直的特殊情况，比较麻烦。更好的办法或许是计算两个向量的叉积，如果为0，则是平行或者重合的，否则两直线相交。
代码就不贴了，直接调用上面的函数就ok了。


三.判断两线段相交
经典方法，就是跨立试验了，即如果一条线段跨过另一条线段，则线段的两个端点分别在另一条线段的两侧。但是，还需要检测边界情况，即两条线段中可能某条线段的某个端点正好落在另一条线段上。这也是算法导论中介绍的算法。
程序模拟如下：

int direction(point* pi, point* pj, point* pk{ 
     point p1, p2; 
     
     p1.x = pk->x - pi->x; 
     p1.y = pk->y - pi->y; 
    
     p2.x = pj->x - pi->x; 
     p2.y = pj->y - pi->y; 
     
    return crossProduct(&p1, &p2); 
} 

int onSegment(point* pi, point* pj, point* pk{ 
    int minx, miny, maxx, maxy; 
    if (pi->x > pj->x){ 
         minx = pj->x; 
         maxx = pi->x;    
     }else{ 
         minx = pi->x; 
         maxx = pj->x; 
     } 
     
     if (pi->y > pj->y){ 
         miny = pj->y; 
         maxy = pi->y;    
     }else{ 
         miny = pi->y; 
         maxy = pj->y; 
     } 
     
     if (minx <= pk->x && pk->x <= maxx && miny <= pk->y && pk->y <= maxy) 
        return 1; 
     else 
        return 0; 
} 
    
int segmentIntersect(point* p1, point* p2, point* p3, point* p4){ 
    int d1 = direction(p3, p4, p1); 
    int d2 = direction(p3, p4, p2); 
    int d3 = direction(p1, p2, p3); 
    int d4 = direction(p1, p2, p4); 
    if (d1 * d2 < 0 && d3 * d4 < 0) 
        return 1; 
    else if (!d1 && onSegment(p3, p4, p1)) 
        return 1; 
    else if (!d2 && onSegment(p3, p4, p2)) 
        return 1; 
    else if (!d3 && onSegment(p1, p2, p3)) 
        return 1; 
    else if (!d4 && onSegment(p1, p2, p4)) 
        return 1; 
    else 
        return 0; 
} 

实际上，如果想改进上述算法，还可以在跨立试验前加一步，就是先做快速排斥试验。那就是，先分别判断以两条线段为对角线的矩形是否相交，如果不相交，则两个线段肯定不相交。

四.判断两条线段相交，然后计算交点
设一条线段为L0=P1P2, 另一条线段或直线为L1=Q1Q2, 要计算的就是L0和L1的交点。

1.首先判断L0和L1是否相交(方法已在前文讨论过), 如果不相交则没有交点, 否则说明L0和L1一定有交点, 下面就将L0和L1都看作直线来考虑.

2.如果P1和P2横坐标相同, 即L0平行于Y轴
a)若L1也平行于Y轴
    i.若P1的纵坐标和Q1的纵坐标相同, 说明L0和L1共线, 假如L1是直线的话他们有无穷的交点, 假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点(该方法在前文已讨论过);
    ii.否则说明L0和L1平行, 他们没有交点;
b)若L1不平行于Y轴, 则交点横坐标为P1的横坐标, 代入到L1的直线方程中可以计算出交点纵坐标;

3.如果P1和P2横坐标不同, 但是Q1和Q2横坐标相同, 即L1平行于Y轴, 则交点横坐标为Q1的横坐标, 代入到L0的直线方程中可以计算出交点纵坐标;

4.如果P1和P2纵坐标相同, 即L0平行于X轴
a)若L1也平行于X轴,
    i.若P1的横坐标和Q1的横坐标相同, 说明L0和L1共线, 假如L1是直线的话他们有无穷的交点, 假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点(该方法在前文已讨论过);
    ii.否则说明L0和L1平行, 他们没有交点;
b)若L1不平行于X轴, 则交点纵坐标为P1的纵坐标, 代入到L1的直线方程中可以计算出交点横坐标;

5.如果P1和P2纵坐标不同, 但是Q1和Q2纵坐标相同, 即L1平行于X轴, 则交点纵坐标为Q1的纵坐标, 代入到L0的直线方程中可以计算出交点横坐标;

6.剩下的情况就是L1和L0的斜率均存在且不为0的情况
a)计算出L0的斜率K0, L1的斜率K1;
b)如果K1 = K2
    i.如果Q1在L0上, 则说明L0和L1共线, 假如L1是直线的话有无穷交点, 假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点(该方法在前文已讨论过);
    ii.如果Q1不在L0上, 则说明L0和L1平行, 他们没有交点.
c)联立两直线的方程组可以解出交点来
这个算法并不复杂, 但是要分情况讨论清楚, 尤其是当两条线段共线的情况需要单独考虑, 所以在前文将求两条共线线段的算法单独写出来. 另外, 一开始就先利用矢量叉乘判断线段与线段(或直线)是否相交, 如果结果是相交, 那么在后面就可以将线段全部看作直线来考虑. 需要注意的是, 我们可以将直线或线段方程改写为ax+by+c=0的形式, 这样一来上述过程的部分步骤可以合并, 缩短了代码长度, 但是由于先要求出参数, 这种算法将花费更多的时间

设num[i]表示第i个数，sum[i][j]表示num[i]到num[j]的和，dp[i][j]表示从i到j,先取数者可以得到的最大值。

状态转移方程：

dp[i][j] = max( num[i]+sum[i+1][j]-dp[i+1][j], num[j]+sum[i][j-1]-dp[i][j-1] );

状态转移方程:  dp[i][j] = dp[i][j] && dp[i+1][j] && dp[i][j+1] && dp[i+1][j+1]  , 时间复杂度O(n^3);

     摘要: 用dist[x1][y1][x2][y2]表示点(x1,y1)到点(x2,y2)的最短距离, 用BFS枚举求得.枚举所有集合点, 先考虑王和马分别到集合点的距离和.再考虑王走1步, 枚举其中一只马到去接王, 再到集合点, 其他马各自到集合点的距离.再考虑王走2步的情形. /**//*ID: loreleiTASK: camelotLANG: C++*/#includ...  阅读全文
最多有5种商品，把每一种优惠，把他们看成分别有5个权重（w1,w2,w3,w4,w5），一种价值cost的背包。

另外也把原价购买一件商品作为一种背包，例如（w1=1，w2..5=0）cost=3
 

PS:最近忙着写标书，真是廉价劳动力哇。。

这道题是要求我们求出一条欧拉路，所以我们要首先判断图中是否有欧拉路。

对于一个无向图，如果它每个点的度都是偶数，那么它存在一条欧拉回路；

如果有且仅有2个点的度为奇数，那么它存在一条欧拉路；
如果超过2个点的度为奇数，那么它就不存在欧拉路了。

SPFA  + SLF

SLF：Small Label First 策略。
实现方法是，设队首元素为 ，队列中要加入节点 ，在 时加到队首而不是队尾，否则和普通的 SPFA 一样加到队尾。

LLL：Large Label Last 策略。
实现方法是，设队列 中的队首元素为 ，距离标号的平均值为 ，每次出队时，若 ，把 移到队列末尾，如此反复，直到找到一个 使 ，将其出队。

     摘要: 康托hash + BFS /**//*ID: lorelei3TASK: msquareLANG: C++*/#include <fstream>#include <memory.h>#include <algorithm>#include <functional>#includ...  阅读全文

其实就是解线性方程.

用克莱姆法则求解, 求解过程要判断是否是分数解或者负解。

Ax = k*B   枚举B, 从1到100.