Tag Archives: 解析几何

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

Posted on by

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;
}




圈地(斜率排序+坐标系旋转)

Posted on by

Problem 2 圈地(land.cpp/c/pas)

【题目描述】

2维平面上有n个木桩，你有一次圈地的机会并得到圈到的土地，为了体现你的高风亮节，你要使你圈到的土地面积尽量小。圈地需要圈一个至少3个点的多边形，多边形的顶点就是一个木桩，圈得的土地就是这个多边形内部的土地。

 

【输入格式】

第一行一个整数n，表示木桩个数。
　　接下来n行，每行2个整数表示一个木桩的坐标，坐标两两不同。

【输出格式】

仅一行，表示最小圈得的土地面积，保留2位小数。

【样例输入】

样例1：
3

0 0

0 1

1 0

样例2：
4

0 0

0 1

0 2

1 1

【样例输出】

样例1：
0.50
样例2：
0.00
【数据范围】

    对于10%的数据，n<=100；
　对于30%的数据，n<=300；
　对于50%的数据，n<=500；
　对于100%的数据，n<=1000。

显然这题的多边形一定是三角形。

首先求出所有边，按k排序（必须先求出来，不能直接在排序的时候求）

然后考虑这些边，会发现正好是绕坐标系旋转一圈。

也就是说如果按照以这边为y轴从左至右排序，那么每转移一条边，只需要调换该边2个点的位置

这题没给范围，但是必须用long long

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
using namespace std;
#define MAXN (1000+10)
#define INF (1000000000)
#define eps 1e-10
struct P
{
	int x,y;
	long long operator*(const P &b)
	{
		return (long long)x*b.y-(long long)b.x*y;
	}
	friend bool operator<(P a,P b){if (a.x^b.x)	return a.x<b.x;return a.y<b.y;}
}a[MAXN];
long long abs2(long long x){if (x>0) return x;return -x;}
int n,h[MAXN];
struct E
{
	int i,j;
	double k;
	E(){}
	E(int _i,int _j):i(_i),j(_j){if (a[i].x==a[j].x) k=1e10;else k=(double)(a[i].y-a[j].y)/(a[i].x-a[j].x);}
	friend bool operator<(E a,E b){return a.k<b.k;	}
}e[MAXN*MAXN/2];
long long S2(P A,P B,P C)
{
	return abs2(A*B+B*C+C*A);
}
int size=0;
int main()
{
	freopen("land.in","r",stdin);
	freopen("land.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
	long long ans=(long long)1<<60;
	/*
	for (int i=1;i<=n-2;i++)
		for (int j=i+1;j<n;j++)
			for (int k=j+1;k<=n;k++)
				ans=min(ans,abs2(a[i]*a[j]+a[j]*a[k]+a[k]*a[i]));
	*/

	sort(a+1,a+1+n);
	for (int i=1;i<=n;i++) h[i]=i;
	for (int i=1;i<n;i++)
		for (int j=i+1;j<=n;j++)
		{
			e[++size]=E(i,j);
		}

	sort(e+1,e+1+size);

	for (int i=1;i<=size&&ans;i++)
	{
		if (h[e[i].i]>1&&h[e[i].i]<n) ans=min(ans,S2(a[h[e[i].i]-1],a[h[e[i].i]],a[h[e[i].i]+1]));
		if (h[e[i].j]>1&&h[e[i].j]<n) ans=min(ans,S2(a[h[e[i].j]-1],a[h[e[i].j]],a[h[e[i].j]+1]));
		swap(a[h[e[i].i]],a[h[e[i].j]]);
		swap(h[e[i].i],h[e[i].j]);
	}

	printf("%.2lf",(double)ans/2);
	return 0;
}


Tyvj P2053（线段覆盖‘s精度误差&析构函数）

Posted on by

众所周知，精度误差是很坑人的东西

而且有的时候有了eps反而会错（考虑你的条件是严苛还是放宽）

从 0 到  x0 的覆盖中，点的排序就是一例

：

首先要尽可能以x排序，然后左端点尽量靠右

但是左端点会爆误差……所以先考虑 端点的误差是否可以忽略，如果不行就算相等)

第二处是排序的对象

理论上是从0到x0 不合条件的都被赋0了……

但是 有可能出现 0<x0<a[i].x<a[i+7].x这样的 整条线段不在里面的情况 此时若用max min 那么 会忽略左端点 (我们的本意是让不在区间内的点的区间删了-要删就全删）

故 需考虑·这样的情况

 <-最右边的黄色和青色的

第三处是答案（终极精度误差）   你要让最左端点<eps和最右端点<x0-eps 这里的限制应为严苛（倘若放宽，最左端点为0（前面已经让它∈[0.x0]）都不行的话  会出现永远不可能的情况 


#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXX (10000+10)
#define MAXH (100+10)
#define MAXN (2*7+10)
double h,x0,m;
const double eps=1e-10;
bool cmp(const double a,const double b);
bool equal(const double a,const double b)
{
	if (-eps<a-b&&a-b<eps) return 1;
	else return 0;
}
struct node  //表示线段端点 y=1表示左端点 y=-1有端点
{
	double x,y;
	node():x(0.0),y(0.0){}
	node(double _x,double _y):x(_x),y(_y){}
	friend bool operator<(const node a,const node b){return equal(a.x,b.x)?a.y>b.y:cmp(a.x,b.x);/*(a.y!=b.y)?a.y>b.y:a.x+eps<b.x||a.x-eps<b.x;*/ /* ? */	}
}a[MAXN];
double x[MAXN],r[MAXN];
bool cmp(const double a,const double b)
{
//	cout<<(a-eps<b)<<endl;
	return ((a-eps<b)||(a+eps<b));
}
bool is_ok(double m)
{
	for (int i=1;i<=7;i++)
	{
		if (h<=r[i]+m)
		{
			double dis=sqrt(pow((r[i]+m),2)-pow((h),2));
		//	if (dis<0) cout<<dis<<' ';
			a[i].x=max(0.0,x[i]-dis);a[i+7].x=min(x0,x[i]+dis);
		//	if (max(0.0,x[i]-dis)>min(x0,x[i]+dis)) cout<<x[i]-dis<<' '<<x[i]+dis;

		}
		else a[i].x=a[i+7].x=0;
		if (a[i].x>a[i+7].x) a[i].x=a[i+7].x=0;
		a[i].y=1;a[i+7].y=-1;
	}
//	for (int i=1;i<=14;i++) cout<<a[i].x<<' '<<a[i].y<<endl;
	sort(a+1,a+1+14);
//	for (int i=1;i<=14;i++) cout<<a[i].x<<' '<<a[i].y<<endl;

	for (int i=1,j=0;i<14;i++)
	{
		j+=a[i].y;
		if (!j) return 0;
	}
//	if (cmp(0.0,a[1].x)||cmp(a[14].x,x0)) return 0;
	if ((eps<a[1].x)||(a[14].x<x0-eps)) return 0;
	return 1;
}
int main()
{
//	freopen("rainbow.in","r",stdin);
	scanf("%lf%lf",&h,&x0);
	for (int i=1;i<=7;i++) scanf("%lf%lf",&x[i],&r[i]);

//	for (int i=1;i<=7;i++) cout<<r[i]<<' ';

/*	node a=node(3.0,-1.0);
	node b=node(2.0,-1.0);
	cout<<(a<b)<<endl;
*/
	double l=0.0,r=x0+h+1;
//	cout<<is_ok(60.0);
	while (r-l>eps)
	{
		double m=(l+r)/2;
		if (is_ok(m)) r=m;
		else l=m;
	}
	printf("%.2lfn",r);

//	while (1);
	return 0;
}



POJ 2588(解析几何+并查集）

Posted on by

题目就是早从左到右的路

注意输入的实数

这题图画好就行，别像我一开始把图弄反就成

从上开始找，若找到一个与下边界相邻的就无解，找到与左边相邻的记圆与左边界相交的下边的点（相当于左上角挖去一块），右边同理。

Program snake;
const
   maxn=1000;
var
   n,i,j:longint;
   x,y,r,lc,rc:array[1..maxn] of double;
   maxl,maxr:double;
   father:array[1..maxn] of longint;
   b,up,down,left,right:array[1..maxn] of boolean;
function getfather(x:longint):longint;
begin
   if father[x]=x then exit(x);
   father[x]:=getfather(father[x]);
   exit(father[x]);
end;
Procedure union(x,y:longint);
begin
   father[father[x]]:=father[father[y]];
end;
function distance(i,j:longint):double;
begin
   exit(sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j])));
end;
function dis(x1,y1,x2,y2:double):double;
begin
   exit(sqrt(sqr(x1-x2)+sqr(y1-y2)));
end;

begin
   fillchar(b,sizeof(b),false);
   fillchar(up,sizeof(up),false);
   fillchar(down,sizeof(down),false);
   fillchar(left,sizeof(left),false);
   fillchar(right,sizeof(right),false);
   fillchar(lc,sizeof(lc),0);
   fillchar(rc,sizeof(rc),0);
   maxl:=1000;maxr:=1000;

   read(n);
   for i:=1 to n do
   begin
      read(x[i],y[i],r[i]);
      father[i]:=i;
      for j:=1 to i-1 do
         if distance(i,j)<r[i]+r[j] then
            if getfather(i)<>getfather(j) then
               union(i,j);
      if (y[i]<r[i]) then down[i]:=true;
      if (y[i]+r[i]>1000) then up[i]:=true;
      if (x[i]<r[i]) then
      begin
         left[i]:=true;
         lc[i]:=y[i]-sqrt(sqr(r[i])-sqr(x[i]));
      end;
      if (x[i]+r[i]>1000) then
      begin
         right[i]:=true;
         rc[i]:=y[i]-sqrt(sqr(r[i])-sqr(1000-x[i]));
      end;

   end;
   for i:=1 to n do
      if (up[i]) and not(b[i]) then
      begin
         for j:=1 to n do
            if father[i]=father[j] then
            begin
               b[j]:=true;
               if (down[j]) then
               begin
                  writeln('Bill will be bitten.');
                  halt;
               end;
               if left[j] then
               begin
                  if lc[j]<maxl then maxl:=lc[j];

               end;
               if right[j] then
               begin
                  if rc[j]<maxr then maxr:=rc[j];
               end;


            end;
      end;
   writeln('Bill enters at (0.00, ',maxl:2:2,') and leaves at (1000.00, ',maxr:2:2,').');




end.