3335.cpp

pku 3335 北大ACM网站上的算法题

// test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <iostream>
#include <algorithm>
using namespace std;

#define MAXN 101

struct POINT
{
	int x,y;
};
POINT ptList[MAXN+1];
//POINT dirList[MAXN+1];//可省略
struct Edge
{
	char idx;
	int XDir() const
	{	return ptList[idx+1].x-ptList[idx].x;}
	int YDir() const
	{	return ptList[idx+1].y-ptList[idx].y;}
	bool operator<(const Edge& p)
	{
		int diff=XDir()*p.YDir()-p.XDir()*YDir();
		if(diff) return diff>0;//级角从小到大(向左转)
		POINT dir2;
		dir2.x=ptList[idx].x-ptList[p.idx].x;
		dir2.y=ptList[idx].y-ptList[p.idx].y;
		return dir2.x*p.YDir()<p.XDir()*dir2.y;//取靠左的，不考虑共线情况
	}
	bool operator==(const Edge& p)
	{
		return XDir()*p.YDir()==p.XDir()*YDir();
	}
};

int T,n;
Edge edges[MAXN+1];
//检查输入顺序，若为顺时针，将点逆序
void CheckDir()
{
	//查看最高点的拐向，向左拐说明是逆时针
	int i=0;
	int yMax=ptList[0].y,idxMax=0;
	for (i=1;i<n;i++)
	{
		if(ptList[i].y>yMax)
		{
			yMax=ptList[i].y;idxMax=i;
		}
	}
	POINT dir1,dir2;
	if(idxMax==0)
	{
		dir1.x=ptList[0].x-ptList[n-1].x;
		dir1.y=ptList[0].y-ptList[n-1].y;
	}
	else 
	{
		dir1.x=ptList[idxMax].x-ptList[idxMax-1].x;
		dir1.y=ptList[idxMax].y-ptList[idxMax-1].y;
	}	
	dir2.x=ptList[idxMax+1].x-ptList[idxMax].x;
	dir2.y=ptList[idxMax+1].y-ptList[idxMax].y;
	if(dir1.x*dir2.y<dir2.x*dir1.y||dir1.x*dir2.y==dir2.x*dir1.y&&dir1.x>0)//顺时针，勿忘共线情况
	{
		int low=0,high=n-1;
		while(low<high)
		{
			POINT pt=ptList[low];
			ptList[low]=ptList[high];
			ptList[high]=pt;
			low++;high--;
		}
		ptList[n]=ptList[0];
	}
}

void EdgeSort()
{//按级角排序
	int i;
	CheckDir();
	int low=0,high=n-1;
	for(i=0;i<n;i++)
	{
		int xDir=ptList[i+1].x-ptList[i].x;
		int yDir=ptList[i+1].y-ptList[i].y;
		if(yDir>0||yDir==0&&xDir>0)
			edges[low++].idx=i;
		else edges[high--].idx=i;
	}
	sort(edges,edges+low);
	sort(edges+low,edges+n);
	int num=0;
	for (i=1;i<n;i++)
	{
		if(edges[num]==edges[i])
			continue;
		edges[++num]=edges[i];
	}
	n=++num;
}
//edge1与edge2的交点在edge的左侧返回true，否则返回false
bool PtInLeft(Edge& edge1,Edge& edge2,Edge& edge)
{
	//直线
	int a1=edge1.YDir();
	int b1=-edge1.XDir();
	int c1=ptList[edge1.idx].x*a1+ptList[edge1.idx].y*b1;

	int a2=edge2.YDir();
	int b2=-edge2.XDir();
	int c2=ptList[edge2.idx].x*a2+ptList[edge2.idx].y*b2;
	//交点
	double y=(a1*c2-a2*c1)*1.0/(a1*b2-a2*b1);
	double x=a1?((c1-b1*y)*1.0/a1):((c2-b2*y)*1.0/a2);
	//
	double xdir2,ydir2;
	xdir2=x-ptList[edge.idx].x;
	ydir2=y-ptList[edge.idx].y;
	return xdir2*edge.YDir()<=edge.XDir()*ydir2;//注意有等于号，共线也属于做半平面
}
struct mydeque
{
	enum{SIZE=60};
	Edge* buffer[SIZE];
	int front,rear;
	mydeque():front(0),rear(0){}
	void push_back(Edge* a)
	{
		buffer[rear++]=a;
		rear=rear==SIZE?0:rear;
	}
	void pop_back()
	{rear=rear?(rear-1):SIZE-1;}
	void pop_front()
	{front=(front==SIZE-1)?0:front+1;}
	int size()
	{
		int size=rear-front;
		return size<0?(size+SIZE):size;
	}
	Edge* top(int i)
	{
		int idx=rear-i-1;
		idx=idx<0?(idx+SIZE):idx;
		return buffer[idx];
	}
	Edge* bottom(int i)
	{
		int idx=front+i;
		idx=(idx>=SIZE)?(idx-SIZE):idx;
		return buffer[idx];
	}
};
bool Check()
{
	int i;
	EdgeSort();
	mydeque deq;
	deq.push_back(&edges[0]);deq.push_back(&edges[1]);
	for (i=2;i<n;i++)
	{
		while (deq.size()>=2&&!PtInLeft(*deq.top(0),*deq.top(1),edges[i]))
			deq.pop_back();
		while (deq.size()>=2&&!PtInLeft(*deq.bottom(0),*deq.bottom(1),edges[i]))
			deq.pop_front();
		deq.push_back(&edges[i]);
	}
	if(deq.size()<3)
		return false;
	bool flag=true;
	while(deq.size()>2&&flag)
	{
		flag=false;
		while (deq.size()>2&&!PtInLeft(*deq.top(0),*deq.top(1),*deq.bottom(0)))
		{
			flag=true;
			deq.pop_back();
		}
		while (deq.size()>2&&!PtInLeft(*deq.bottom(0),*deq.bottom(1),*deq.top(0)))
		{
			flag=true;
			deq.pop_front();
		}
	}
	return deq.size()>2;
}

int main(int argc, char* argv[])
{
	scanf("%d",&T);
	for (int i=0;i<T;i++)
	{
		scanf("%d",&n);
		for (int j=0;j<n;j++)
		{
			scanf("%d%d",&ptList[j].x,&ptList[j].y);
		}
		ptList[n]=ptList[0];
		if(Check())
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}