[bzoj1007]-[HNOI2008]水平可见直线

发布于 2017-09-16  4 次阅读



题目(BZOJ)
先填坑在这,之后再更。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#define eps 1e-8
using namespace std;
struct edge{
	double k;
	double b;
	int no;
}e[50005];
int n;
bool ans[50005];
bool cmp(const edge &x,const edge &y)
{
	if (fabs(x.k-y.k)<eps) return x.b<y.b;
	return x.k<y.k;
}
double cx(edge a,edge b)
{
	return (double)(b.b-a.b)/(a.k-b.k);
}
int top;
edge s[50005];
void insert(edge x)
{
	while (top)
	{
		if (fabs(s[top].k==x.k)) --top;
		else if (top>1 && cx(x,s[top-1])<=cx(s[top],s[top-1]))
			--top;
		else break;
	}
	s[++top]=x;
}
int main()
{
	scanf(
	for (int i=1;i<=n;++i)
		scanf(
		e[i].no=i;
	sort(e+1,e+n+1,cmp);
	for (int i=1;i<=n;++i) insert(e[i]);
	for (int i=1;i<=top;++i) ans[s[i].no]=true;
	for (int i=1;i<=n;++i)
		if (ans[i]) printf(
	return 0;
}