判断线段相交

刚刚开始接触计算几何.. 之前按自己的思路写了一个线段相交却怎么也过不了某题..

最后发现果然还是自己智商拙计= =..

线段a, b相交的充要条件是:  a 叉积 b 的两个端点之积为负, b 叉积 a 的两个端点之积为负数, 而且两线段不平行.

下面给出部分代码.

bool Parallel(Point a, Point b, Point c, Point d) {return !dcmp(a.cross(b, a + d - c));}

bool SegCross(Point& a, Point& b, Point& c, Point& d)
{
    //一定要判断是否平行!
    if( !Parallel(a, b, c, d) && a.cross(b, c) * a.cross(b, d) <= 0 && c.cross(d, a) * c.cross(d, b) <= 0)
        return true;
    return false;
}

某知识点列表=w=…

 一、动态规划
LCS
LIS
背包
单调性DP
环形DP
树形DP
状态压缩DP

二、搜索
枚举
搜索与剪枝
启发式搜索
DLX
双向搜索
折半搜索
记忆化搜索
模拟退火

三、计算几何
半平面交
凸包
几何图形的交与并
旋转卡壳
点定位
坐标变换
离散化与扫描
反演
voronoi图
平面图的对偶图
三角剖分
梯形剖分
几何知识

四、贪心

五、树结构
最近公共祖先
生成树
dfs序列
树上倍增
树的分治
树链剖分
link-cut-tree

六、图结构
平面图
二分图
二分图匹配
最短路
差分约束
拓扑排序
网络流
强连通分量
割点割边
欧拉回路
2-sat

七、数论
素数判定
欧几里得算法
不定方程
数位统计
解线性同余方程
baby-step-giant-step
pell方程
大整数质因数分解
勾股方程
积性函数
Fibonacci数列

八、模拟

九、数据结构

队列
链表
单调队列
并查集

平衡树
线段树
树状数组
树套树
四分树
划分树
归并树
kd树
块状链表
hashing
函数式编程

十、博弈论

十一、字符串
kmp
后缀数据结构
trie树
AC自动机
manacher
表达式处理

十二、组合数学
生成函数
容斥原理
康托展开
Catalan数列
Stirling数
polya定理

十三、线性代数
矩阵乘法
高斯消元
线性规划

十四、高精度
FFT

十五、递推

十六、概率论
随机化

十七、经典NPC问题

十八、其它
二分查找
三分查找
双指针扫描
分治
分块
RMQ
快速幂
数学
排序
构造

POJ 3304 Segments 计算几何基础,点的表示和叉积

题意:给出n条线段,求是否有一条直线能够与全部线段相交.

由于一条穿过所有的线段的直线,总可以通过平移来使得其通过某两个端点,故枚举端点,判断过端点的直线是否能穿过所有线段即可.

此题WA几次..究其原因为: 叉积之前需要判断给出的向量是否为0,为0则不能进行叉积操作..

刚刚开始做计算几何…orz各路神犇..希望能够快快长进!

# include <iostream>
# include <cmath>
# define sqr(x) ((x)*(x))
# define rep(x, n) for (int x = 0; x < n; ++x )
using namespace std;

const double eps = 1e-8;
int dcmp(double x){ return (x > eps) - (x < -eps);}

class Point
{
    public:
    double x, y;
    Point(){x = y = 0.0;}
    Point(double a, double b){ x = a; y = b; }

    inline Point operator -(const Point& b)
    { return Point(x-b.x, y-b.y);}

    inline double cross(const Point& b, const Point& c)
    { return (b.x - x) * (c.y - y) - (c.x - x) * (b.y - y); }

    inline double dis(const Point& b)
    { return sqrt( sqr(b.x - x) + sqr(b.y - y) ); }

}line[103][2];

int t, n;
bool ok;

void check(Point& a, Point& b)
{
    if ( dcmp(a.dis(b)) == 0 ) return;
    rep(i, n)
        if ( dcmp(a.cross(b, line[i][0]) * a.cross(b, line[i][1])) > 0 )
            return;
    ok = true;
    return;
}
int main()
{
    double x, y;
    cin >>t;
    while( t-- )
    {
        cin >>n;
        rep(i, n)
        {
            cin >> x >> y;
            line[i][0] = Point(x, y);
            cin >> x >> y;
            line[i][1] = Point(x, y);
        }
        ok = false;
        rep(i, n)
            for (int j = i+1; j < n; ++j )
            {
                if ( ok ) break;
                check(line[i][0], line[j][0]);
                check(line[i][0], line[j][1]);
                check(line[i][1], line[j][0]);
                check(line[i][1], line[j][1]);
            }
        if ( n == 1 ) ok = true;
        if ( ok ) cout << "Yes!" <<endl;
        else cout << "No!" << endl;
    }
    return 0;
}

POJ 2551 Ones 简单的数论

题目所求为。给定一个n,求数列 { 1, 11, 111, 1111… } 第几项可以整除n。

设 x 整除 n,即 x % n == 0。

考虑到: 若 a + b = x,则 x % n == a %n + b % n。。这种奇怪的定理,

于是可以由 x = 1 % n 开始,每次 x = (x * 10 + 1) % n。直到 x %n 为0时,即为这个数。

# include <iostream>
using namespace std;

int n;

int main()
{
    while ( cin >> n )
    {
        int m = 1, c = 1;
        while ( m % n )
        {
            m = (m*10 + 1) % n ;
            ++c;
        }
        cout << c <<endl;
    }
    return 0;
}