首页 > 代码库 > HDU 4946 Area of Mushroom 凸包 第八次多校

HDU 4946 Area of Mushroom 凸包 第八次多校

2024-07-17 15:38:30   218人阅读

Problem Description
Teacher Mai has a kingdom with the infinite area.

He has n students guarding the kingdom.

The i-th student stands at the position (xi,yi), and his walking speed is vi.

If a point can be reached by a student, and the time this student walking to this point is strictly less than other students, this point is in the charge of this student.

For every student, Teacher Mai wants to know if the area in the charge of him is infinite.
 

Input
There are multiple test cases, terminated by a line "0".

For each test case, the first line contains one integer n(1<=n<=500).

In following n lines, each line contains three integers xi,yi,vi(0<=|xi|,|yi|,vi<=10^4).
 

Output
For each case, output "Case #k: s", where k is the case number counting from 1, and s is a string consisting of n character. If the area in the charge of the i-th student isn‘t infinite, the i-th character is "0", else it‘s "1".
 

Sample Input
3
0 0 3
1 1 2
2 2 1
0
 

Sample Output
Case #1: 100
 

Source
2014 Multi-University Training Contest 8

比赛的时候，忘了去重了 ，wa出翔


#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>

#define INF 1e9
#define maxn 1000
#define EPS 1e-6

#define N 1000
using namespace std;
struct point
{
    int x,y;  //横纵坐标 : x,y
    double len,theta;  //与参考点的距离 len 与参考点构成的向量与 (1,0)向量构成的夹角的余弦值 theta
}g[N]; //定义了一个全局变量，记录凸包中的点
/*--------按余弦值，从大到小快速排序--------*/
void qsort(int st,int en)
{
    int i=st,j=en;
    g[0]=g[i];
    while(i<j)
    {
        while(i<j && g[0].theta>=g[j].theta) j--;
        if(i<j) { g[i]=g[j]; i++; }
        while(i<j && g[0].theta<=g[i].theta) i++;
        if(i<j) { g[j]=g[i]; j--; }
    }
    g[i]=g[0];
    if(st<i-1) qsort(st,i-1);
    if(i+1<en) qsort(i+1,en);
}

/*-----------Graham 扫描法-------------*/
void graham(int *n)
{
    /*第一步，寻找y坐标最小，然后x坐标最小的点*/
    int p=1;
    for(int i=2;i<=*n;i++)
      if((g[i].y<g[p].y)||(g[i].y==g[p].y && g[i].x<g[p].x)) p=i;
    g[0]=g[p]; g[p]=g[1]; g[1]=g[0];
    /*找到该点，并把它存放在 g 中的第一个元素的位子上*/
    
    /*第二步，计算所有的点距离参考点的距离(len) 还有夹角的余弦值 (theta)*/
    for(int i=2;i<=*n;i++)
    {
        g[i].len=sqrt((g[i].x-g[1].x)*(g[i].x-g[1].x)+(g[i].y-g[1].y)*(g[i].y-g[1].y));
        g[i].theta=100*(g[i].x-g[1].x)/g[i].len;
    }
    qsort(2,*n);//先根据夹角的余弦值从大到小排序
    
    /*第三步，将所有theta值相等的点，只保存len值最大的，存放在数组map中*/
    point map[N];
    int tot=0; p=1;
    while(p<=*n)
    {
        int k=p;
        while(fabs(g[p].theta-g[p+1].theta)<=EPS)
        {
            if(g[p+1].len>g[k].len) k=p+1;
            p++;
        }
        map[++tot]=g[k];
        p++;
    }
    
    /*第四步，对map中的元素扫描一遍，确定凸包的元素，放在数组g中*/
    *n=tot; tot=3; //先做了一个小小的处理，使得自己更好理解
    memset(g,0,sizeof(g));
    g[1]=map[1]; g[2]=map[2]; g[3]=map[3]; //先将前三个点入栈 g 
    for(int i=4;i<=*n;i++)  //依次用map中的每个点对g中的点进行一次判断，看是否是属于凸包
    {
        double chaji=(g[tot].x-g[tot-1].x)*(map[i].y-g[tot].y)-(map[i].x-g[tot].x)*(g[tot].y-g[tot-1].y);
        for(;chaji<=0 && tot>=1;) //如果旋转的方向不同，g[tot]这个点就不是，删除,并继续判断 g 中下一个点是不是
        {
            tot--;
            chaji=(g[tot].x-g[tot-1].x)*(map[i].y-g[tot].y)-(map[i].x-g[tot].x)*(g[tot].y-g[tot-1].y);
        }
        g[++tot]=map[i]; //将map[i]这个点入栈，至于是否是属于凸包中的点，等待以后的点来判断
    }
    *n=tot;//凸包处理完，总共有tot个凸包上的点
}







/*---------------------------------------------------------------------------------------------*/

struct Node{
	int x,y,v,rank,bl;
}tmp;
int maxe;
vector<Node> stu;
int cas=0;
bool cmp(Node a,Node b)
{
	return a.rank<b.rank;
}
void init(int n)
{
	stu.clear();
	maxe=0;
	for(int i=0;i<n;i++)
	{
		scanf("%d %d %d",&tmp.x,&tmp.y,&tmp.v);
		tmp.rank=i;
		tmp.bl=0;
		stu.push_back(tmp);
		maxe=max(tmp.v,maxe);
	}
}
bool check(int a,int b,int tt)
{
	int c;
	if(b==tt)
	{
		c=1;
	}else 
	{
		c=b+1;
	}
	 double chaji=(g[c].x-g[b].x)*(stu[a].y-g[c].y)-(stu[a].x-g[c].x)*(g[c].y-g[b].y);
	 if(chaji<=EPS) return 1;
	 else return 0;
}

int main()
{
	//freopen("data.in","r",stdin);
	int n;
	while (~scanf("%d",&n))
	{	
		if(n==0) break;
		printf("Case #%d: ",++cas);
		init(n);
		
		
		
		
		if(maxe==0)
		{
			for(int i=0;i<n;i++)
			{
				printf("0");
			}
		}
		else 
		{
			for(int i=0;i<n;i++)
			{
				if(stu[i].v==maxe)
				{
					stu[i].bl=1;
				}
			}
			for(int i=0;i<n-1;i++)
			{
				if(stu[i].bl==1)//错误写法: if(stu[i].v=maxe)
				{
					for(int j=i+1;j<n;j++)
					{
						if(stu[i].x==stu[j].x&&stu[i].y==stu[j].y&&stu[i].v==stu[j].v&&i!=j)
						{
							stu[j].bl=0;
							stu[i].bl=-1;
						}
					}
				}
			}
			int tt=0;
			for(int i=0;i<n;i++)
			{
				if(stu[i].v==maxe&&stu[i].bl!=0)
				{	g[++tt].x=stu[i].x;
					g[tt].y=stu[i].y;
				}
			}
			//printf("%d\n",tt);
			if(tt>=3)
			{
				graham(&tt);
				for(int i=0;i<n;i++){
					if(stu[i].bl==1){
						stu[i].bl=0;
						for(int j=1;j<=tt;j++)
						{
							if((stu[i].x==g[j].x&&stu[i].y==g[j].y)||check(i,j,tt))
							{
								stu[i].bl=1;
								break;
							}
						}
					}
				}
			}
			sort(stu.begin(),stu.end(),cmp);
			for(int i=0;i<n;i++)
			{
				if(stu[i].bl==-1)
					stu[i].bl=0;
				printf("%d",stu[i].bl);
			}
		}

		
		puts("");
	}
	return 0;
}


联系
我们