POJ 1981 最大点覆盖问题(极角排序)
Time Limit: 5000MS | Memory Limit: 30000K | |
Total Submissions: 8346 | Accepted: 2974 | |
Case Time Limit: 2000MS |
Description
Fig 1. Circle and Points
Input
You may assume 1 <= N <= 300, 0.0 <= X <= 10.0, and 0.0 <= Y <= 10.0. No two points are closer than 0.0001. No two points in a data set are approximately at a distance of 2.0. More precisely, for any two points in a data set, the distance d between the two never satisfies 1.9999 <= d <= 2.0001. Finally, no three points in a data set are simultaneously very close to a single circle of radius one. More precisely, let P1, P2, and P3 be any three points in a data set, and d1, d2, and d3 the distances from an arbitrarily selected point in the xy-plane to each of them respectively. Then it never simultaneously holds that 0.9999 <= di <= 1.0001 (i = 1, 2, 3).
Output
Sample Input
3
6.47634 7.69628
5.16828 4.79915
6.69533 6.20378
6
7.15296 4.08328
6.50827 2.69466
5.91219 3.86661
5.29853 4.16097
6.10838 3.46039
6.34060 2.41599
8
7.90650 4.01746
4.10998 4.18354
4.67289 4.01887
6.33885 4.28388
4.98106 3.82728
5.12379 5.16473
7.84664 4.67693
4.02776 3.87990
20
6.65128 5.47490
6.42743 6.26189
6.35864 4.61611
6.59020 4.54228
4.43967 5.70059
4.38226 5.70536
5.50755 6.18163
7.41971 6.13668
6.71936 3.04496
5.61832 4.23857
5.99424 4.29328
5.60961 4.32998
6.82242 5.79683
5.44693 3.82724
6.70906 3.65736
7.89087 5.68000
6.23300 4.59530
5.92401 4.92329
6.24168 3.81389
6.22671 3.62210
0
Sample Output
2
5
5
11
Source
N^2枚举,保存每段弧的极角范围及端点方向,然后按上端点在前,下端点在后,从大到小对极角排序,从头扫描一遍。
若经过上端点:ans++ 否则:ans--,取ans最大值即可。
代码:
//#include"bits/stdc++.h"
#include<sstream>
#include<iomanip>
#include"cstdio"
#include"map"
#include"set"
#include"cmath"
#include"queue"
#include"vector"
#include"string"
#include"cstring"
#include"time.h"
#include"iostream"
#include"stdlib.h"
#include"algorithm"
#define db double
#define ll long long
#define vec vectr<ll>
#define mt vectr<vec>
#define ci(x) scanf("%d",&x)
#define cd(x) scanf("%lf",&x)
#define cl(x) scanf("%lld",&x)
#define pi(x) printf("%d\n",x)
#define pd(x) printf("%f\n",x)
#define pl(x) printf("%lld\n",x)
//#define rep(i, x, y) for(int i=x;i<=y;i++)
#define rep(i, n) for(int i=0;i<n;i++)
const int N = 1e4+ ;
const int mod = 1e9 + ;
const int MOD = mod - ;
const int inf = 0x3f3f3f3f;
const db PI = acos(-1.0);
const db eps = 1e-;
using namespace std;
struct P
{
db x,y;
db ang;
bool in;
};
P a[N],b[N];
db dis(P a,P b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int cmp(P a,P b){
if(a.ang==b.ang) return a.in>b.in;//上端点在前
return a.ang>b.ang;
}
int main()
{
int n;
while(scanf("%d",&n)==,n)
{
int ans=;
for(int i=;i<=n;i++) cd(a[i].x),cd(a[i].y);
for(int i=;i<=n;i++)
{
int p=;
for(int j=;j<=n;j++){
if(i==j||dis(a[i],a[j])>2.0+eps) continue;
db ang=atan2(a[i].x-a[j].x,a[i].y-a[j].y);//i于j的极角
db tha=acos(dis(a[i],a[j])/2.0);//极角波动范围
b[p].ang=ang+tha+*PI,b[p++].in=;//上端点
b[p].ang=ang-tha+*PI,b[p++].in=;//下端点
}
sort(b,b+p,cmp);
int tmp=;
for(int j=;j<p;j++){
if(b[j].in==) tmp++;
else tmp--;
ans=max(tmp,ans);
}
}
pi(ans);
}
return ;
}
最新文章
- Pyhont-Urllib2
- Examples of MIB Variables - SNMP Tutorial
- 一些小题<;代码>;
- easyui 之ComboTree 用法Demo
- [C#] 與Android共舞–手機post資料給Server (转帖)
- tomcat文件服务配置
- Windows 上远程访问 Unix 的 XWindow / XManager / X
- Python-memcached的基本使用
- [LeetCode#266] Palindrome Permutation
- JSP具体篇——out
- 淘宝接口实现ip归属地查询
- 关于LD_DEBUG (转载)
- Widget小组件
- Redis设计与实现读书笔记——双链表
- 初学者应学会如何加快seo
- 3624: [Apio2008]免费道路
- 基于nmap扫描结果的端口爆破工具:BrutesPray
- php中文件操作常用函数有哪些
- 【MySQL】MySQL层级数据的递归遍历
- Linux写时拷贝技术【转】