noj 1099 rectilinear polygon.txt

ACM资料大集合

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;

//NOJ 1099 Rectilinear polygon
//bearch,qsort的使用
//思路：存在性
//1.一条水平线上的点一定有偶数个，竖直线上的也是
//2.假设水平线上有点x1,x2,x3,x4...,x2n-1,x2n,则x1x2,x3x4,x2n-1x2n分别连成一条竖线
//3.由于题目中给的点是90度多边形的顶点，故顶点一定连接且仅连接一条横线
//  和一条竖线，故若多边形存在，则沿着顶点一横一竖地找，
//  回到原点的同时也编列了所有的点。周长就在编列的同时求。
/*
输入：
1
8
1 2
1 0
2 1
2 2
3 2
3 1
4 0
4 2

输出
12
*/
#define NMAX 100005
typedef struct point
{
	int x;
	int y;
	int left;
	//若为1，表示点位于水平方向上的线段的左边，若为-1，则是右边
	int up;
	//若为1，表示点位于竖直方向上的线段的上面，若为-1，则是下面
}point;

bool cmpx(point a,point b)
{
	return a.x<b.x||(a.x==b.x&&a.y<b.y);
}

bool cmpy(point a,point b)
{
	return a.y<b.y||(a.y==b.y&&a.x<b.x);
}

int bbmx(const void *a,const void *b)
{
	if( ((point *)a)->x!=( (point *)b)->x) return ((point *)a)->x-((point *)b)->x;
	else return ((point *)a)->y-((point *)b)->y;
}

int bbmy(const void *a,const void *b)
{
	if( ((point *)a)->y!=( (point *)b)->y) return ((point *)a)->y-((point *)b)->y;
	else return ((point *)a)->x-((point *)b)->x;
}

point tem1[NMAX];//水平位置为主序
point tem2[NMAX];//竖直位置为主序
point shuru[NMAX];

int findx(point x,int num)
{//返回x在tem1[]中的位置
	point *p;
	p=(point *)bsearch(&x,tem1+1,num,sizeof(point),bbmx);
	return p-tem1;
}

int findy(point y,int num)
{//返回y在tem2[]中的位置
	point *p;
	p=(point *)bsearch(&y,tem2+1,num,sizeof(point),bbmy);
	return p-tem2;
}

int solve(int num)
{
	int i,start,tt;
	long sql=0;
	point t1,t2,t3,	startp;
	if(num%2==1) return -1;//奇数点，KA掉
	for(i=1;i<=num;i++) tem1[i]=tem2[i]=shuru[i];
	sort(tem1+1,tem1+1+num,cmpx);
	sort(tem2+1,tem2+1+num,cmpy);
	for(i=1;i<=num;i+=2)
	{
		if(tem1[i].x!=tem1[i+1].x) return -1;//水平位置的点奇数个，KA掉
		tem1[i].up=-1;tem1[i+1].up=1;//标位于水平线段的位置
	}
	for(i=1;i<=num;i+=2)
	{
		if(tem2[i].y!=tem2[i+1].y) return -1;//同上
		tem2[i].left=1;tem2[i+1].left=-1;//标位于竖直线段的位置
	}
	start=1;
	startp=tem1[start];
	for(i=1;i<=num;i+=2)
	{//每轮先从竖方向找，再从横方向走
		t1=tem1[start];
		if(t1.up==1) t2=tem1[start-1];//往下走
		else t2=tem1[start+1];//往上走
		if(t1.x!=t2.x) return -1;
		sql+=abs(tem1[start].y-t2.y);
		tt=findy(t2,num);//找到t2这个点在水平数组里的下标
		t2=tem2[tt];
		if(t2.left==1) t3=tem2[tt+1];//往右走
		else t3=tem2[tt-1];//往左走
		if(t2.y!=t3.y) return -1;
		sql+=abs(tem2[tt].x -t3.x );
		start=findx(t3,num);//找到t3这个点在竖直数组里的下标，同时进行下一轮的寻路
		if(i!=num-1&&t3.x==startp.x&&t3.y ==startp.y) return -1;//对应思路3 
	}
	return sql;
}
int main()
{
	int i,casenum,j,num;
	scanf("%d",&casenum);
	for(i=1;i<=casenum;i++)
	{
		scanf("%d",&num);
		for(j=1;j<=num;j++)
		{
			scanf("%d%d",&shuru[j].x,&shuru[j].y );
		}
		cout<<solve(num)<<endl;
//		for(j=1;j<=num;j++)
//		{
//			cout<<findx(shuru[j],num)<<endl;
//		}
	}
	return 0;
}


/*
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

struct point {
    int x;
    int y;
    int v;
    int h;
};
struct point p[110000];

struct point *pv[110000];
struct point *ph[110000];
int pts;

int comp1(const void * p1, const void * p2) {
    if( ((point *)(p1))->x !=  ((point *)(p2))->x)
		return ((point *)(p1))->x -  ((point *)(p2))->x;
    return ( (point *)(p1))->y -  ((point *)(p2))->y;
}
int comp2(const void *p1, const void *p2) {
    if( ( (point *)(p1))->y !=( (point *) (p2))->y)
		return ( (point *)(p1))->y -  ((point *)(p2))->y;
    return ( (point *)(p1))->x - ( (point *)(p2))->x;
}
int findv(struct point* pp) {
    struct point** ret = (point **)bsearch(&pp, pv, pts, sizeof(pv[0]), comp1);
    //printf("%p\n", ret);
    return ret - pv;
}
int findh(struct point* pp) {
    struct point** ret =  (point **)bsearch(&pp, ph, pts, sizeof(ph[0]), comp2);
    //printf("%p\n", ret);
    return ret - ph;
}

int main() {
    int cases;
    int i;
    int x;
    int y;
	   int j = 0;
       int len = 0;
    scanf("%d", &cases);
    while(cases--) {
        scanf("%d", &pts);
        for(i = 0; i < pts; i++) {
            scanf("%d %d", &x, &y);
            p[i].x = x;
            p[i].y = y;
            pv[i] = &p[i];
            ph[i] = &p[i];
        }
        qsort(pv, pts, sizeof(pv[0]), comp1);
        qsort(ph, pts, sizeof(ph[0]), comp2);
        if(pts % 2) goto impossible;
        for(i = 0; i < pts; i+=2) {
            pv[i]->v = 1;
            pv[i+1]->v = -1;
            if(pv[i]->x != pv[i+1]->x) goto impossible;
            ph[i]->h = 1;
            ph[i+1]->h = -1;
            if(ph[i]->y != ph[i+1]->y) goto impossible;
        }
        for(i = 0; i < pts; i+=2)
		{
            //printf("%d %d\n", p[j].x, p[j].y);
            int h = findh(p+j);
            int oldh = h;
            if(p[j].h == 1) h++; else h--;
            len += abs(ph[h]->x- ph[oldh]->x);
            //printf("%d\n", abs(ph[h]->x- ph[oldh]->x));
            j = ph[h] - p;
            //printf("%d %d\n", p[j].x, p[j].y);
            int v = findv(p+j);
            int oldv = v;
            if(p[j].v == 1) v++; else v--;
            len += abs(pv[v]->y- pv[oldv]->y);
            //printf("%d\n", abs(pv[v]->y- pv[oldv]->y));
            j = pv[v] - p;
            if(j == 0 && i != pts-2) goto impossible;
        }
        printf("%d\n", len);
        continue;
impossible:
        printf("-1\n");
    }
	return 0;
}
*/