UVALive 7461 Separating Pebbles （计算几何）

Separating Pebbles

题目链接：

http://acm.hust.edu.cn/vjudge/contest/127401#problem/H

Description

http://7xjob4.com1.z0.glb.clouddn.com/1e1638de1146450534631815cbf822c6

Input

The first line of the input contains an integer K (K ≤ 20) indicating the number of test cases. The first line of each test case consists of an integer N (N ≤ 250) indicating the number of pebbles. The next N lines each contains a triplet (x, y, c), where x and y represent the x and y coordinates (all integers, 0 ≤ x, y ≤ 150) of a pebble point, and c represents the type of pebble: ‘o’ denoted by ‘0’ and ‘+’ denoted by ‘1’.

Output

For each test case, output ‘1’ if Dr. Y can separate the pebbles with a single straight line; if not, output ‘0’.

Sample Input

2 5 1 2 0 2 1 0 4 3 1 5 4 1 6 3 1 4 1 2 0 2 1 0 1 1 1 2 2 1

Sample Output

1 0
##题意：给出平面上的两类点，判断是否能画一条直线将两类点完全分割开来.
##题解：枚举任意两点组成的直线, 除了在直线上的点以外，若其余点满足分居两侧的要求，那么我只要稍微旋转一下这条直线就能满足要求. 对直线上点的特殊考虑：当直线上有若干点时，如果出现两个'o'点中间夹一个'x'的情况是无法旋转的. 所以能旋转的条件是直线上不会出现两种类型的点间隔分布. 对重点的特殊考虑：如果有重点的话，特判可能会比较多，所以干脆一开始对所有点去重. 若有两个不同类型的点重叠，那么一定不能划分. (坑爹的是，题目的数据好像并没有重复点，在uDebug上跑类型不同的重点居然输出1). 不知不觉就打了5000B的代码，稍有点繁琐...
##代码： ``` cpp #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define double long long #define eps 1e-8 #define maxn 300 #define mod 100000007 #define inf 0x3f3f3f3f #define mid(a,b) ((a+b)>>1) #define IN freopen("in.txt","r",stdin); using namespace std;

struct Point{
double x,y;
int tp;
Point(){}
Point(double tx,double ty) {x=tx;y=ty;}
bool operator<(const Point& b)const
{
if(x==b.x) return y<b.y;
return x<b.x;
}
}tmp[maxn];

vector p;

struct Line{
Point a,b;
};

int sign(double x)
{
if(!x) return 0;
return x<0? -1:1;
}

double xmul(Point p0,Point p1,Point p2)
{return (p1.x-p0.x)(p2.y-p0.y)-(p2.x-p0.x)(p1.y-p0.y);}

bool is_inline(Point a, Point b, Point c) {
return xmul(a,b,c) == 0;
}

/判两点在线段异侧,点在线段上返回0/
int opposite_side(Point p1,Point p2,Line l)
{
return sign(xmul(p1,l.a,l.b)*xmul(p2,l.a,l.b))<0;
}

int same_side(Point p1,Point p2,Line l)
{
return sign(xmul(p1,l.a,l.b)*xmul(p2,l.a,l.b))>0;
}

/判断两点是否重合/
int equal_point(Point p1,Point p2)
{
return (sign(p1.x-p2.x)0)&&(sign(p1.y-p2.y)0);
}

int vis[200][200];

int main(int argc, char const *argv[])
{
//IN;

int t; cin >> t;
while(t--)
{
    int n; scanf("%d", &n);
    memset(vis, -1, sizeof(vis));
    p.clear(); p.push_back(Point(0,0));
    bool flag = 1;
    int m = 0;
    for(int i=1; i<=n; i++) {
        scanf("%lld %lld %d", &tmp[i].x, &tmp[i].y, &tmp[i].tp);
    }
    //sort(p+1, p+1+n);

    /*去重*/
    for(int i=1; i<=n; i++) {
        if(vis[tmp[i].x][tmp[i].y] == -1) {
            vis[tmp[i].x][tmp[i].y] = tmp[i].tp;
            p.push_back(tmp[i]);
            m++;
        } else {
            if(vis[tmp[i].x][tmp[i].y] != tmp[i].tp) {
                flag = 0;
                break;
            }
        }
    }

    if(!flag) {  /*如果有两类点重叠，无法划分*/
        printf("0
");
        continue;
    }

    vector<int> in;  /*在直线上的点*/
    vector<int> a;   /*A类点'o'*/
    vector<int> b;   /*B类点'x'*/
    for(int i=1; i<=m; i++) {
        for(int j=i+1; j<=m; j++) {
            flag = 1;
            Line l;  l.a = p[i]; l.b = p[j];
            a.clear(); b.clear(); in.clear();
            
            for(int k=1; k<=m; k++) {
                if(is_inline(p[i], p[j], p[k])) {   /*在直线上*/
                    in.push_back(k);
                    continue;
                }
                if(p[k].tp == 0) {
                    if(a.empty()) {
                        a.push_back(k);
                        if(!b.empty()) {  
                            /*因为只能维护是否在同一边而不能具体到是左边还是右边，所以要判断集合中的第一个点是否违背条件，样例2可以说明这一点*/
                            if(same_side(p[k],p[b[0]],l)) {
                                flag = 0;
                                break;
                            }
                        }
                    } else {
                        if(opposite_side(p[a[0]],p[k],l)) {
                            flag = 0;
                            break;
                        }
                        else a.push_back(k);
                    }
                    continue;
                }
                if(p[k].tp == 1) {
                    if(b.empty()) {
                        b.push_back(k);
                        if(!a.empty()) {
                            if(same_side(p[k],p[a[0]],l)) {
                                flag = 0;
                                break;
                            }
                        }
                    } else {
                        if(opposite_side(p[b[0]],p[k],l)) {
                            flag = 0;
                            break;
                        }
                        else b.push_back(k);
                    }
                    continue;
                }
            }
            if(!flag) continue;

            /*对直线上的点判断是否有"间隔出现"的情况*/
            sort(in.begin(), in.end());
            int sz = in.size();
            bool change = 0;
            int last = p[in[0]].tp;
            for(int k=1; k<sz; k++) {
                if(p[in[k]].tp != last) {
                    if(!change) {
                        last = p[in[k]].tp;
                        change = 1;
                    }
                    else {
                        flag = 0;
                        break;
                    }
                }
            }

            if(flag) {
                //printf("%d %d
", i,j);
                goto las;
            }
        }
    }

    las:
    if(flag) printf("1
");
    else printf("0
");
}

return 0;

}