zkx06111's Blog

//总结：细节决定成败。
//判断是否输出-1的部分break,continue细节弄错错了好久
//大致思路：对于每个岛，x正负sqrt(d^2-y^2)的线段上的点都可以包含
//所以就是对于n条线段进行区间取点问题。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#define sqr(x) (x)*(x)
using namespace std;

struct Point{
	double x;
	double y;
}p[1000];

bool cmp(Point a,Point b){
	if (a.y!=b.y) return a.y<b.y;
	return a.x>b.x;
}

int main()
{
	int c=0,n,d;
	while (cin>>n>>d){
		if (n==0 && d==0) break;
    bool flag=false;
		for (int i=0;i<n;++i){
			cin>>p[i].x>>p[i].y;
			if (!flag && p[i].y>d){
				cout<<"Case "<<(++c)<<": -1\n";
        flag=true;
			}
			double t=sqrt(sqr(d)-sqr(p[i].y));
			p[i].y=p[i].x;
			p[i].x-=t; p[i].y+=t;
		}
    if (flag) continue;

		sort(p,p+n,cmp);
		int ans=1;
		double cur=p[0].y;
		for (int i=1;i<n;++i)
			if (cur<p[i].x){
				cur=p[i].y; ++ans;
			}
		cout<<"Case "<<(++c)<<": "<<ans<<endl;
	}
	return 0;
}

//敲了一遍就过，开心^_^
#include <iostream>
#include <algorithm>
using namespace std;

int m,n,k,l,d;

struct str
{
	int order; //序号
	int value; //该行（或列）讲话的人数
	str() {
		value=0;
	}
}row[1000],col[1000];

bool cpv(str a,str b)
{
	return a.value>b.value; //以讲话人数为关键字，显然优先把人多的分开
}

bool cpo(str a,str b)
{
	return a.order<b.order; //按照题目要求，按序号从小到大输出
}

int main()
{
	cin>>m>>n>>k>>l>>d;
	for (int i=1;i<m;++i) row[i].order=i;
	for (int i=1;i<n;++i) col[i].order=i; //初始化序号
	for (int i=0,x,y,p,q;i<d;++i) {
		cin>>x>>y>>p>>q;
		if (x==p) col[min(y,q)].value++; //若行号相同则在该列说话人数加一，下同
		else row[min(x,p)].value++; 
	}
	sort(row+1,row+m+1,cpv); sort(row+1,row+k+1,cpo); //两边排序后，row[1..k]就是答案，下同
	sort(col+1,col+n+1,cpv); sort(col+1,col+l+1,cpo);
	for (int i=1;i<k;++i) cout<<row[i].order<<' '; cout<<row[k].order<<endl; //注意行尾无空格
	for (int i=1;i<l;++i) cout<<col[i].order<<' '; cout<<col[l].order;
	return 0;
}