分类目录归档:ACM-POJ

POJ 1696 Space Ant 稍微修改的卷包裹法.

题目大意为,给定一些点,以最下且最左的那个点位起点,只能左拐,且路径不能交叉,求使得路径经过点数最多的走法.输出这条路径的长度和按顺序经过的点.

显然,只要沿着最外围走,所有点都可以被走到,使用求凸包的卷包裹法稍加更改,即可走出这样一条路径.

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

int t, n;

class Point
{
    public:
    double x, y;
    int id;
    Point(){x = 0; y = 0;}

    Point(const double& x, const double& y, const int id = 0)
    { this->x = x; this->y = y; this->id = id; }

    inline bool operator <(const Point& a)const
    { return (y - a.y)? y < a.y : x < a.x; }

    inline Point operator +(const Point& a)
    { return Point(x + a.x, y + a.y); }

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

    inline double dot(const Point& a)
    { return x * a.x + y * a.y; }

    inline double Dis(const Point& a)
    { return sqrt( (*this - a).dot(*this - a)); }

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

}p[53];

bool v[53];
int res[53];

int main()
{
    int q;
    double x, y;
    cin >> t;
    while ( t-- )
    {
        cin >> n;
        rep(i, n)
        {
            cin >> q >> x >> y;
            p[i] = Point(x, y, q);
            v[i] = false;
        }
        sort(p, p+n);
        v[0] = true;
        res[0] = 0;
        rep(i, n-1)
        {
            rep(j, n)
                if ( !v[j] )
                    res[i+1] = j;
            rep(j, n)
            {
                if ( v[j] ) continue;
                double tmp = p[res[i]].cross(p[res[i+1]], p[j]);
                if ( tmp < 0 )
                    res[i+1] = j;
            }
            v[res[i+1]] = true;
        }
        cout << n;
        rep(i, n)
            cout << ' '<< p[res[i]].id;
        cout << endl;
    }
    return 0;
}

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;
}

POJ 2309 BST

此题一看,树状数组里神奇的 n & -n 就派上用场了。

输入你,输出 n-(n&-n)+1 和 n+(n&-n)-1 即可。

当然可以用一个递归来划分区间。同样我也写了一下。。比上面的方法可慢了不少。。

# include <iostream>
using namespace std;

int t, n;

void dfs(long long root, long long min, long long max)
{
    if ( root == n )
    {
        cout << min << " " << max << endl;
        return;
    }
    if ( n < root )
        dfs((root+min)>>1, min, root-1);
    else dfs( ((root+max)>>1)+1, root+1, max );
}

int main()
{
    cin >> t;
    while ( t-- )
    {
        cin >> n;
        dfs((1<<30), 1, 2147483647);
    }
    return 0;
}

POJ 2528 线段树

本体思路其实很简单,离散化后线段树段修改,最后统计一遍即可。

不过此题数据甚是恶心,HASH改了好几遍才AC,想想以后离散化还是不用HASH比较好= =。。

不过也借由此题促使咱回去看《统计的力量》熟悉重口味版线段树,收获良多>u<。。

# include <cstdio>
# include <algorithm>
# include <cstring>
using namespace std;
const int MOD = 50007;
int t, n;

struct POST
{
	int l, r, id;
	bool show;
	POST(){ show = false; }
}p[10003];

int list[40003], tot, f[MOD+2], trans[MOD+2];
int hash(int x)
{
	int pos;
	pos = (3*x + x%107 + x>>2) % MOD;
	while ( f[pos] && f[pos] != x ) pos = (pos + 173)%MOD;
	if ( pos < 0 ) pos += MOD;
	return pos;
}

int M, tree[131077], tf[131007], time;
const int tsize = sizeof(tree), fsize = sizeof(f);
void modify(int s, int t, int c)
{
	++time;
	for ( s+=M-1, t+=M+1; s^t^1; s>>=1, t>>=1 )
	{
		if (~s&1 ) tree[s^1] = c, tf[s^1] = time;
		if ( t&1 ) tree[t^1] = c, tf[t^1] = time;
	}
}
void ask(int x, int mt, int c)
{
	if ( x <= M + tot && tree[x] && tf[x] > mt ) c = tree[x], mt = tf[x];
	if ( x >= M )
	{
		if (c) p1.show = true;
		return ;
	}
	ask(x<<1, mt, c);
	ask((x<<1)+1, mt, c);
}

void work()
{
	int i, a, b;
	tot = time = 0;
	memset(f, 0, sizeof(f));
	scanf("%d", &n);
	if ( n == 0 )
	{
		printf("0\n");
		return ;
	}
	for ( i = 1; i <= n; ++i ) scanf("%d%d", &p[i].l, &p[i].r);
	for ( i = 1; i <= n; ++i )
	{
		p[i].id = i;
		p[i].show = false;
		a = hash(p[i].l);
		b = hash(p[i].r);
		if ( !f[a] ) f[a] = p[i].l, list[++tot] = p[i].l;
		if ( !f[b] ) f[b] = p[i].r, list[++tot] = p[i].r;
	}
	sort(list+1, list+1+tot);
	a = tot;
	for (i = 1; i < a; ++i )
		if ( list[i] + 1 < list[i+1] ) list[++tot] = list[i] + 1;
	sort(list+1, list+1+tot);

	for ( i = 1; i <= tot; ++i ) trans[hash(list[i])] = i;
	for ( i = 1; i <= n; ++i )
	{
		p[i].l = trans[hash(p[i].l)];
		p[i].r = trans[hash(p[i].r)];
	}
	for ( M = 1; M < tot+2; M<<=1 );
	memset(tree, 0, tsize);

	for ( i = 1; i <= n; ++i ) modify(p[i].l, p[i].r, p[i].id);
	ask(1, 0, 0);
	for ( a = 0, i = 1; i<= n; ++i ) if ( p[i].show ) ++a;
	printf("%d\n", a);
}

int main()
{
	scanf("%d", &t);
	while ( t-- ) work();
	return 0;
}