POJ 2484(博弈-对称博弈)

A Funny Game
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 3345   Accepted: 1960

Description

Alice and Bob decide to play a funny game. At the beginning of the game they pick n(1 <= n <= 106) coins in a circle, as Figure 1 shows. A move consists in removing one or two adjacent coins, leaving all other coins untouched. At least one coin must
be removed. Players alternate moves with Alice starting. The player that removes the last coin wins. (The last player to move wins. If you can't move, you lose.) 
 

Note: For n > 3, we use c1, c2, ..., cn to denote the coins clockwise and if Alice remove c2, then c1 and c3 are NOT adjacent! (Because there is an empty place between c1 and c3.) 

Suppose that both Alice and Bob do their best in the game. 
You are to write a program to determine who will finally win the game.

Input

There are several test cases. Each test case has only one line, which contains a positive integer n (1 <= n <= 106). There are no blank lines between cases. A line with a single 0 terminates the input. 

Output

For each test case, if Alice win the game,output "Alice", otherwise output "Bob". 

Sample Input

1
2
3
0

Sample Output

Alice
Alice
Bob

Source

POJ Contest,Author:Mathematica@ZSU

博弈第一招——对称博弈。

思路:无论对方怎么取,我都取与它对称(或者相反/一样的)

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cstring>
#include<iostream>
using namespace std;
int main()
{
	int n;
	while(scanf("%d",&n)&&n)
	{
		if (n>=3) cout<<"Bob"<<endl;
		else cout<<"Alice"<<endl;
	}
	return 0;
}

POJ 2362(Square-搜索剪枝1-相对顺序)

Language:
Square
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 17066   Accepted: 5878

Description

Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?

Input

The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.

Output

For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".

Sample Input

3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5

Sample Output

yes
no
yes

Source

《搜索是怎样剪枝的-1》

1.只要找到3条边。

2.从大到小顺序找。

3.每次搜边时要确定边的相对顺序唯一(直接从TLE→秒)


#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXM (20+10)
int tt,n,a[MAXM],cnt,len;
bool b[MAXM],flag;
bool dfs(int l,int x,int pre)
{
//	cout<<l<<' '<<x<<' '<<kth<<endl;
	if (x==len) {l++;x=0;pre=n-1;}
	if (l==4)
	{
		return 1;
	}
	for(int i=pre-1;i;i--)
		if (!b[i]&&x+a[i]<=len)
		{
			b[i]=1;
			if (dfs(l,x+a[i],i)) return 1;
			b[i]=0;
		//	if (!x) return 0;
		}
	return 0;
}
int main()
{
	scanf("%d",&tt);
	while (tt--)
	{
		cnt=0;
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			cnt+=a[i];b[i]=0;
		}
		sort(a+1,a+1+n);
		if (n<4||cnt%4||a[n]>cnt/4)
		{
			printf("non");continue;
		}
		b[n]=1;len=cnt/4;
		if (dfs(1,a[n],n))
		{
			printf("yesn");
		}
		else printf("non");
	}
	return 0;
}


POJ 2553(The Bottom of a Graph-缩点求出度)

Language:
The Bottom of a Graph
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 7308   Accepted: 3003

Description

We will use the following (standard) definitions from graph theory. Let V be a nonempty and finite set, its elements being called vertices (or nodes). Let E be a subset of the Cartesian product V×V, its elements being called edges.
Then G=(V,E) is called a directed graph. 
Let n be a positive integer, and let p=(e1,...,en) be a sequence of length n of edges ei∈E such that ei=(vi,vi+1) for a sequence of vertices (v1,...,vn+1).
Then p is called a path from vertex v1 to vertex vn+1 in G and we say that vn+1 is reachable from v1, writing (v1→vn+1)
Here are some new definitions. A node v in a graph G=(V,E) is called a sink, if for every node w in G that is reachable from vv is also reachable from w. The bottom of a graph is the subset of
all nodes that are sinks, i.e.,bottom(G)={v∈V|∀w∈V:(v→w)⇒(w→v)}. You have to calculate the bottom of certain graphs.

Input

The input contains several test cases, each of which corresponds to a directed graph G. Each test case starts with an integer number v, denoting the number of vertices of G=(V,E), where the vertices will be identified by the integer
numbers in the set V={1,...,v}. You may assume that 1<=v<=5000. That is followed by a non-negative integer e and, thereafter, e pairs of vertex identifiers v1,w1,...,ve,we with
the meaning that (vi,wi)∈E. There are no edges other than specified by these pairs. The last test case is followed by a zero.

Output

For each test case output the bottom of the specified graph on a single line. To this end, print the numbers of all nodes that are sinks in sorted order separated by a single space character. If the bottom is empty, print an empty line.

Sample Input

3 3
1 3 2 3 3 1
2 1
1 2
0

Sample Output

1 3
2

Source

Tarjen缩点统计出度。


#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXN (5000+10)
#define MAXM (1000000+10)
int n,m,h[MAXN],t[MAXN],dfs[MAXN],tim,kind,s[MAXN],tot;
bool b[MAXN];
int edge[MAXM],next[MAXM],pre[MAXN],size;
int x[MAXM],y[MAXM],numk[MAXN];
void addedge(int u,int v)
{
	edge[++size]=v;
	next[size]=pre[u];
	pre[u]=size;
}
void tar(int u)
{
	dfs[u]=t[u]=++tim;b[u]=1;s[++tot]=u;
	for (int p=pre[u];p;p=next[p])
	{
		int &v=edge[p];
		if (!b[v]) tar(v),dfs[u]=min(dfs[u],dfs[v]);
		else if (!h[v]) dfs[u]=min(dfs[u],t[v]);  //保证指向祖先
	}
	if (dfs[u]==t[u])
	{
		kind++;
		while (s[tot]!=u) h[s[tot--]]=kind,numk[kind]++;
		h[s[tot--]]=kind;numk[kind]++;

	}
}
int outdegree[MAXN];
int main()
{
	while (scanf("%d",&n)&&n)
	{
		scanf("%d",&m);
		tot=size=tim=kind=0;
		memset(h,0,sizeof(h));
		memset(t,0,sizeof(t));
		memset(dfs,0,sizeof(dfs));
		memset(s,0,sizeof(s));
		memset(pre,0,sizeof(pre));
		memset(b,0,sizeof(b));
		memset(numk,0,sizeof(numk));
		memset(outdegree,0,sizeof(outdegree));

		for (int i=1;i<=m;i++)
		{
			scanf("%d%d",&x[i],&y[i]);
			addedge(x[i],y[i]);
		}
		for (int i=1;i<=n;i++) if (!b[i]) tar(i);
//		for (int i=1;i<=n;i++) cout<<h[i]<<' ';cout<<endl;
		for (int i=1;i<=m;i++)
		{
			if (h[x[i]]^h[y[i]]) outdegree[h[x[i]]]++;
		}
		/*
		int ans=0;
		for (int i=1;i<=kind;i++)
			if (!outdegree[i]) ans+=numk[i];
		cout<<ans<<endl;
		*/
		bool flag=0;
		for (int i=1;i<=n;i++)
			if (!outdegree[h[i]])
			{
				if (flag) printf(" ");else flag=1;printf("%d",i);
			}


	//	cout<<ans<<endl;
		cout<<endl;
	}
	return 0;
}

BZOJ 2732([HNOI2012]射箭-半平面交)

2732: [HNOI2012]射箭

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 186  Solved: 104
[Submit][Status][Discuss]

Description

沫沫最近在玩一个二维的射箭游戏,如下图 1 所示,这个游戏中的 x 轴在地面,第一象限中有一些竖直线段作为靶子,任意两个靶子都没有公共部分,也不会接触坐标轴。沫沫控制一个位于(0,0)的弓箭手,可以朝 0 至 90?中的任意角度(不包括 0度和 90度),以任意大小的力量射出带有穿透能力的光之箭。由于游戏中没有空气阻力,并且光之箭没有箭身,箭的轨迹会是一条标准的抛物线,被轨迹穿过的所有靶子都认为被沫沫射中了,包括那些 只有端点被射中的靶子。这个游戏有多种模式,其中沫沫最喜欢的是闯关模式。在闯关模式中,第一关只有一个靶
子,射中这个靶子即可进入第二关,这时在第一关的基础上会出现另外一个靶子,若能够一箭 双雕射中这两个靶子便可进入第三关,这时会出现第三个靶子。依此类推,每过一关都会新出 现一个靶子,在第 K 关必须一箭射中前 K 关出现的所有 K 个靶子才能进入第 K+1 关,否则游戏 结束。沫沫花了很多时间在这个游戏上,却最多只能玩到第七关“七星连珠”,这让她非常困惑。 于是她设法获得了每一关出现的靶子的位置,想让你告诉她,最多能通过多少关

Input

输入文件第一行是一个正整数N,表示一共有N关。接下来有N行,第i+1行是用空格隔开的三个正整数xi,yi1,yi2(yi1<yi2 ),表示第i关出现的靶子的横坐标是xi,纵坐标的范围是从yi1到yi2 。 
 输入保证30%的数据满足N≤100,50%的数据满足N≤5000,100%的数据满足N≤100000且给 出的所有坐标不超过109 。 
 

Output

仅包含一个整数,表示最多的通关数。 

Sample Input

5


2 8 12

5 4 5

3 8 10

6 2 3

1 3 7

Sample Output

3

HINT

先把方程写出来,改一改。
然后在坐标系上做半平面交。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<functional>
#define MAXN (100000+10)
#define MAXCi (1000000000)
#define eps 1e-15
#define For(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n;
struct P
{
	double x,y;
	P(){}
	P(double _x,double _y):x(_x),y(_y){}
}p[MAXN*4];
struct V
{
	double x,y;
	V(){}
	V(double _x,double _y):x(_x),y(_y){}
	V(P a,P b):x(b.x-a.x),y(b.y-a.y){}
	friend double operator*(V a,V b){return a.x*b.y-a.y*b.x;}
	friend V operator*(double a,V b){return V(a*b.x,a*b.y);}
	friend P operator+(P a,V b){return P(a.x+b.x,a.y+b.y);}
};
struct line
{
	P p;
	V v;
	double ang;
	int i;
	line(){}
	line(double _x,double _y,double _a,double _b,int _i):p(P(_x,_y)),v(V(_a,_b)),i(_i){ang=atan2(v.y,v.x);}
	bool onleft(P A)
	{
		return v*V(p,A)>=0;
	}
	bool operator<(const line& l) const
	{
		return ang<l.ang;
	}
	friend P getinter(line a,line b)
	{
		/*
		V u=V(a.p,b.p);
		double t=(a.v*u)/(b.v*a.v);
		return b.p+(t*b.v);
		double s1=V(a.p,b.p+b.v)*a.v;
		double s2=a.v*V(a.p,b.p);
		return b.p+(-s1/(s1+s2))*b.v;
//		V u=V(a.p,b.p);
		*/
		V u=V(b.p,a.p);
		double t=(b.v*u)/(a.v*b.v);
		return a.p+t*a.v;

	}
}que[MAXN*10],q[MAXN*4];
int size=0;
int half_intersection(line *l,int n)
{
	int first=1,last=0;
	for (int i=1;i<=size;i++)
	{
		if (l[i].i>n) continue;
		if (!last) {q[++last]=l[i];continue;}
		while (first<last&&!l[i].onleft(p[last-1])) last--;
		while (first<last&&!l[i].onleft(p[first])) first++;
		if (fabs(q[last].v*l[i].v)<=eps)
		{
			if (q[last].onleft(l[i].p)) q[last]=l[i];
		}
		else q[++last]=l[i];
		if (first<last) p[last-1]=getinter(q[last-1],q[last]);
	}
	bool flag=1;
	while (flag)
	{
		flag=0;
		while (first<last&&!q[first].onleft(p[last-1])) last--,flag=1;
		while (first<last&&!q[last].onleft(p[first])) first++,flag=1;
	}
	/*
	p[last]=getinter(q[last],q[first]);
	for (int i=first;i<=last;i++)
		printf("%lf %lfn",p[i].x,p[i].y);
	cout<<endl;
	*/
	return last-first>1;
}
void pri(line a,line b)
{
	P c=getinter(a,b);
	printf("%.lf %.lfn",c.x,c.y);
}
int main()
{
	freopen("archery.in","r",stdin);
	freopen("archery.out","w",stdout);
	cin>>n;
	que[1]=line(0,0,0,1,0);
	que[2]=line(-1,0,1,0,0);
	que[3]=line(0,MAXCi,-1,0,0);
	que[4]=line(-MAXCi,MAXCi,0,-1,0);size=4;
//	pri(que[3],que[4]);
//	size=0;
	for (int i=1;i<=n;i++)
	{
		double x,l,r;
		scanf("%lf%lf%lf",&x,&l,&r);
		que[++size]=line(0,l/x,1/x,-1,i);
		que[++size]=line(0,r/x,-1/x,1,i);
	}
	sort(que+1,que+1+size);
//	cout<<size<<endl;
//	for (int i=l;i<=r;i++) cout<<halsf_intersection(que,i)<<' ';
//	cout<<half_intersection(que,50001);
	int l=0,r=n,Mid=0;
	while (l<=r)
	{
		int mid=(l+r)>>1;
		if (half_intersection(que,mid)) {Mid=mid;l=mid+1;}else r=mid-1;
	}
	cout<<Mid<<endl;
	return 0;
}

BZOJ 2241([SDOI2011]打地鼠-二分判断+贪心)

Description

打地鼠是这样的一个游戏:地面上有一些地鼠洞,地鼠们会不时从洞里探出头来很短时间后又缩回洞中。玩家的目标是在地鼠伸出头时,用锤子砸其头部,砸到的地鼠越多分数也就越高。

游戏中的锤子每次只能打一只地鼠,如果多只地鼠同时探出头,玩家只能通过多次挥舞锤子的方式打掉所有的地鼠。你认为这锤子太没用了,所以你改装了锤子,增加了锤子与地面的接触面积,使其每次可以击打一片区域。如果我们把地面看做M*N的方阵,其每个元素都代表一个地鼠洞,那么锤子可以覆盖R*C区域内的所有地鼠洞。但是改装后的锤子有一个缺点:每次挥舞锤子时,对于这R*C的区域中的所有地洞,锤子会打掉恰好一只地鼠。也就是说锤子覆盖的区域中,每个地洞必须至少有1只地鼠,且如果某个地洞中地鼠的个数大于1,那么这个地洞只会有1只地鼠被打掉,因此每次挥舞锤子时,恰好有R*C只地鼠被打掉。由于锤子的内部结构过于精密,因此在游戏过程中你不能旋转锤子(即不能互换RC)。

你可以任意更改锤子的规格(即你可以任意规定RC的大小),但是改装锤子的工作只能在打地鼠前进行(即你不可以打掉一部分地鼠后,再改变锤子的规格)。你的任务是求出要想打掉所有的地鼠,至少需要挥舞锤子的次数。

Hint:由于你可以把锤子的大小设置为1*1,因此本题总是有解的。

Input

 第一行包含两个正整数MN

下面M行每行N个正整数描述地图,每个数字表示相应位置的地洞中地鼠的数量。

Output

输出一个整数,表示最少的挥舞次数。

Sample Input

3 3



1 2 1



2 4 2



1 2 1



Sample Output



4



【样例说明】



使用2*2的锤子,分别在左上、左下、右上、右下挥舞一次。



【数据规模和约定】





对于100%的数据,1<=M,N<=100,其他数据不小于0,不大于10^5

二分判断+贪心

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#define MAXN (100+10)
#define INF (1000000000)
#define For(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n,m,a[MAXN][MAXN],a2[MAXN][MAXN];
int is_ok(int l,int r)
{
	memcpy(a2,a,sizeof(a));
	int sum=0;
	For(i,n-l+1) For(j,m-r+1)
		if(a2[i][j])
		{
			int delta=a2[i][j];sum+=delta;
			for (int k=i;k<=i+l-1;k++)
				for (int k2=j;k2<=j+r-1;k2++)
					if (a2[k][k2]<delta) return 0;
					else a2[k][k2]-=delta;
		}
	return sum;
}
int main()
{
	scanf("%d%d",&n,&m);
	int cnt=0,ans=0;
	For(i,n) For(j,m) {scanf("%d",&a[i][j]);cnt+=a[i][j];}
	For(i,n) For(j,m)
	{
		if (i*j<ans) continue;
		if (!(cnt%(i*j))&&is_ok(i,j)*i*j==cnt)
		{
			ans=i*j;
		}
	}
	cout<<cnt/ans<<endl;
	return 0;
}

BZOJ 2705([SDOI2012]Longge的问题-欧拉函数φ(i))

2705: [SDOI2012]Longge的问题

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 375  Solved: 239
[Submit][Status][Discuss]

Description

Longge的数学成绩非常好,并且他非常乐于挑战高难度的数学问题。现在问题来了:给定一个整数N,你需要求出∑gcd(i, N)(1<=i <=N)。

Input

一个整数,为N。

Output

一个整数,为所求的答案。

Sample Input

6

Sample Output

15

HINT

【数据范围】

对于60%的数据,0<N<=2^16。

对于100%的数据,0<N<=2^32。

 

欧拉函数

枚举n的约数k,令s(k)为满足gcd(m,n)=k,(1<=m<=n)  m的个数,则ans=sigma(k*s(k)) (k为n的约数)

 因为gcd(m,n)=k,所以gcd(m/k,n/k)=1,于是s(k)=euler(n/k)

 枚举n的约数即可,复杂度o(sqrt(n))

PS:刚刚ksy告诉我C++,直接读int比读char转int慢(——0)



#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
#include<iostream>
using namespace std;
#define MAXN (2<<31)
long long ans=0,n;
long long phi(long long n)
{
	if (n==1) return 1;
//	cout<<n;
	long long ans=1;
	for (long long i=2;i*i<=n;i++)
		if (n%i==0)
		{
			int k=0;
			while (n%i==0) {k++,n/=i;}
			ans*=i-1;
			for (int j=2;j<=k;j++) ans*=i;
		}
	if (n>1) ans*=n-1;
//	cout<<' '<<ans<<endl;
	return ans;
}
int main()
{
	cin>>n;
	for (int i=1;i*i<=n;i++)
		if (n%i==0)
		{
			ans+=(long long)i*phi(n/i);
			if (i*i<n) ans+=(long long)n/i*phi(i);
		}
	cout<<ans<<endl;
	return 0;
}

CH 白色情人节2(⑤我心永恒-字符串序列个数统计)

背景

You're here, there's nothing I fear,
and I know that my heart will go on.
We'll stay forever this way.
You are safe in my heart.
And my heart will go on and on.

描述

男主想要用三句话表达对女主的爱,男主要对这三句话进行一番锤炼,现在要找出三句话中永恒不变的事物,需要做的,就是计算出三份序列的最长公共子序列长度、公共子序列个数,其中个数对第201314个质数(2769433)取模。字符之间的匹配不区分大小写(即"a"与"A"视为相等)

输入格式

共三行,一行一个字母序列。

输出格式

第一行,三份序列的最长公共子序列长度。
第二行,三份序列的公共子序列个数对第201314个质数(2769433)取模得到的答案

样例输入

INeedYou
IMissYou
ILoveYou

样例输出

4
15

数据范围与约定

对于100%的数据,序列仅含大小写字母,序列长度均leq 100

样例解释

最长公共子序列是IYou,长度为4,公共子序列分别是I Y o u IY Io Iu Yo Yu ou IYo IYu Iou You IYou,共4+6+4+1 = 15个

来源

本题有个无节操版本……

这题是统计公共子序列个数+去重

正解用了容斥原理,并且允许空串。

F[I][J][K]=2F[I-1][J-1][K-1]-F[I'-1][J'-1][K'-1] I',J',K'为I,J,K,之前出现a[i],b[j],c[k]的位置(没有就不用减)

 假设之前已经去重,那么F[I][J][K]只需与F[I'-1][J'-1][K'-1]去重。


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
using namespace std;
#define F (2769433)
#define MAXN (100+10)
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<=n;i++)
int len1,len2,len3,f[MAXN][MAXN][MAXN],pre1[MAXN],pre2[MAXN],pre3[MAXN],s[500];
char a[MAXN],b[MAXN],c[MAXN];
void make_pre(char *a,int n,int *pre)
{
	memset(s,128,sizeof(s));
	memset(pre,0,sizeof(pre));
	For(i,n)
	{
		a[i]=tolower(a[i]);
		pre[i]=s[a[i]];
		s[a[i]]=i;
	}
}
int main()
{
	memset(f,0,sizeof(f));
	scanf("%s%s%s",a+1,b+1,c+1);a[0]=b[0]=c[0]=' ';
	len1=strlen(a)-1,len2=strlen(b)-1,len3=strlen(c)-1;
	make_pre(a,len1,pre1);
	make_pre(b,len2,pre2);
	make_pre(c,len3,pre3);
	int cnt=0;
	For(i,len1)
		For(j,len2)
			For(k,len3)
				if (a[i]==b[j]&&b[j]==c[k]) f[i][j][k]=f[i-1][j-1][k-1]+1;
				else f[i][j][k]=max(max(f[i-1][j][k],f[i][j-1][k]),f[i][j][k-1]);
	cnt=f[len1][len2][len3];
//	memset(f,0,sizeof(f));
	Rep(i,len1) Rep(j,len2) Rep(k,len3) f[i][j][k]=1;
	For(i,len1)
		For(j,len2)
			For(k,len3)
			{
				f[i][j][k]=0;
				if (a[i]==b[j]&&b[j]==c[k])
				{
					f[i][j][k]=(10*F+f[i-1][j-1][k-1]*2)%F;
					if (pre1[i]>0&&pre2[j]>0&&pre3[k]>0) f[i][j][k]=(F+f[i][j][k]-f[pre1[i]-1][pre2[j]-1][pre3[k]-1])%F;
				//	if (!pre1[i]||!pre2[j]||!pre3[k]) f[i][j][k]--;
				}
				else
				{
					f[i][j][k]=(10*F+f[i-1][j][k]+f[i][j-1][k]+f[i][j][k-1]-f[i-1][j-1][k]-f[i][j-1][k-1]-f[i-1][j][k-1]+f[i-1][j-1][k-1])%F;
				}
			}

	printf("%dn%dn",cnt,(F+f[len1][len2][len3]-1)%F);
	return 0;
}


BZOJ 1185([HNOI2007]最小矩形覆盖-旋转卡壳+点集几何意义)

1185: [HNOI2007]最小矩形覆盖

Time Limit: 10 Sec  Memory Limit: 162 MBSec  Special Judge
Submit: 258  Solved: 137

Description

 

l要事先改成r,注意把向量的2点设成同一点会出现奇妙的事情

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
using namespace std;
#define MAXN (50000+10)
#define INF (1000000000)
#define eps 1e-6
struct P
{
	double x,y;
	P(){}
	P(double _x,double _y):x(_x),y(_y){}
	friend bool operator<(P a,P b){return (fabs(a.y-b.y)<eps)?a.x<b.x:a.y<b.y;	}
	friend bool operator==(P a,P b){return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;}
	friend bool operator!=(P a,P b){return !(a==b);}

}a[MAXN],s[MAXN],ansp[5];
int size=0;
double ans=INF;
double dis2(P a,P b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
struct V
{
	double x,y;
	V(){}
	V(double _x,double _y):x(_x),y(_y){}
	V(P a,P b):x(b.x-a.x),y(b.y-a.y){}
	friend double operator*(V a,V b){return	a.x*b.y-a.y*b.x;}
	friend V operator*(double a,V b){return V(a*b.x,a*b.y);}
	friend double operator/(V a,V b){return	a.x*b.x+a.y*b.y;}
	friend P operator+(P a,V b){return P(a.x+b.x,a.y+b.y);}
	friend P operator-(P a,V b){return P(a.x-b.x,a.y-b.y);}
	friend V operator~(V a){return V(a.y,-a.x);}
	double dis2(){return x*x+y*y;	}
}c[MAXN];
int cmp(P A,P B)
{
	double tmp=V(a[1],A)*V(a[1],B);
	if (tmp>0) return 1;
	else if (fabs(tmp)<eps) return (-dis2(A,a[1])-dis2(B,a[1])>0);
	return 0;
}
int n;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
	for (int i=2;i<=n;i++) if (a[i]<a[1]) swap(a[1],a[i]);
	sort(a+2,a+1+n,cmp);
	s[1]=a[1];size=1;
	for (int i=2;i<=n;)
		if (size<2||V(s[size-1],s[size])*V(s[size],a[i])>eps) s[++size]=a[i++];
		else size--;
	s[0]=s[size];

	int l=1,r=1,t=1;
	for (int i=0;i<size;i++)
	{
		while (V(s[i],s[i+1])*V(s[i],s[t+1])-V(s[i],s[i+1])*V(s[i],s[t])>-eps) t=(t+1)%size;
		while (V(s[i],s[i+1])/V(s[i],s[r+1])-V(s[i],s[i+1])/V(s[i],s[r])>-eps) r=(r+1)%size;
		if (i==0) l=r;
		while (V(s[i],s[i+1])/V(s[i],s[l+1])-V(s[i],s[i+1])/V(s[i],s[l])<eps) l=(l+1)%size;
		double Dis2=dis2(s[i],s[i+1]),wlxdis=V(s[i],s[i+1])/V(s[i],s[l]),wrxdis=V(s[i],s[i+1])/V(s[i],s[r]),hxdis=V(s[i],s[i+1])*V(s[i],s[t]);
		double tmp=hxdis*(wrxdis-wlxdis)/Dis2;
		if (tmp<0) tmp=-tmp;
		if (ans>tmp)
		{
			ans=tmp;
			ansp[0]=s[i]-(wlxdis/Dis2)*V(s[i+1],s[i]);
			ansp[1]=s[i]+(wrxdis/Dis2)*V(s[i],s[i+1]);
			ansp[2]=ansp[1]+(hxdis/Dis2)*(~V(s[i+1],s[i]));
			ansp[3]=ansp[0]+(hxdis/Dis2)*(~V(s[i+1],s[i]));
		}
	}
	int p=0;
	for (int i=1;i<4;i++) if (ansp[i]<ansp[p]) p=i;//p=0;
	printf("%.5lfn",ans);
	for (int i=0;i<4;i++)
		printf("%.5lf %.5lfn",ansp[(p+i)%4].x,ansp[(p+i)%4].y);
	return 0;
}

BZOJ 1007(水平可见直线-斜率排序+栈贪心)

1007: [HNOI2008]水平可见直线

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 1830  Solved: 656
[Submit][Status][Discuss]

Description

Input

第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi

Output

从小到大输出可见直线的编号,两两中间用空格隔开,最后一个数字后面也必须有个空格

Sample Input

3

-1 0

1 0

0 0

Sample Output

1 2

按斜率排序,从小到大插入。
半平面交的特殊情况:
每次
都要保证x坐标<x,top>><top,top'> 否则top不可见(top为栈顶元素)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
using namespace std;
#define MAXN (50000+10)
int n;
struct line
{
	int k,b,i;
	friend bool operator<(line a,line b) {return (a.k==b.k)?a.b>b.b:a.k<b.k;	}
	friend double intx(line a,line b)
	{
		return (double)(b.b-a.b)/(a.k-b.k);
	}
}a[MAXN];
int s[MAXN],size=0;
void push(int x)
{
	while (size>1&&intx(a[s[size]],a[s[size-1]])>=intx(a[s[size]],a[x])) size--;
	s[++size]=x;
}
bool b[MAXN];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {scanf("%d%d",&a[i].k,&a[i].b);a[i].i=i;}
	sort(a+1,a+1+n);
	push(1);
	for (int i=2;i<=n;i++)
		if (a[i].k>a[i-1].k) push(i);
//	for (int i=1;)
	memset(b,0,sizeof(b));for (int i=1;i<=size;i++) b[a[s[i]].i]=1;
	for (int i=1;i<=n;i++) if (b[i]) cout<<i<<' ';
	return 0;
}