NC14823. 寄蒜几盒
描述
输入描述
第一行两个正整数n,m和一个正实数L。
接下来n行每行三个实数A,B,C，表示这条直线的方程为Ax+By+C=0
接下来m行，第i行两个实数xi,yi，表示第i个点的坐标。
输出描述
输出m行，每行一个实数，第i行输出的实数表示第i个点所在的区域的面积。保留两位小数。
示例1
输入:
2 4 3 1 1 -1 -1 1 -1 0 2 -2 1 2 1 0 0
输出:
4.00 8.50 8.50 15.00
说明:
对于100%的数据，n<=500,m<=100000C++14(g++5.4) 解法, 执行用时: 897ms, 内存消耗: 97348K, 提交时间: 2019-08-07 16:18:03
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <vector>
#include <map>
#include <set>
using namespace std;
const int mod = 1e5 + 9;
const double eps = 1e-9, pi = acos(-1.);
struct point {
double x, y;
bool operator<(const point &temp) const {
if (fabs(x - temp.x) < eps)
return y < temp.y - eps;
return x < temp.x;
}
};
struct line {
int id;
point l, r;
bool operator<(const line &temp) const {
double lx, rx, mx, y1, y2;
lx = max(l.x, temp.l.x);
rx = min(r.x, temp.r.x);
mx = 0.5 * (lx + rx);
if (fabs(r.x - l.x) < eps)
y1 = 0.5 * (l.y + r.y);
else
y1 = l.y + (mx - l.x) / (r.x - l.x) * (r.y - l.y);
if (fabs(temp.r.x - temp.l.x) < eps)
y2 = 0.5 * (temp.l.y + temp.r.y);
else
y2 = temp.l.y + (mx - temp.l.x) / (temp.r.x - temp.l.x) * (temp.r.y - temp.l.y);
return y1 < y2 - eps;
}
};
int belong[255555][2], cnt_be[255555];
double a[255555], b[255555], c[255555];
struct an {
int l, r;
bool operator<(const an &temp) const {
if (l == temp.l)
return r < temp.r;
return l < temp.l;
// if(l<temp.l)
// return true;
// if(temp.l<l)
// return false;
// return r<temp.r;
}
};
long long fe[mod][33];
int num[mod];
int vl[mod][33];
line lines[550], ls[500000];
set<line> ha;
set<line>::iterator it, ht;
int cnt_ls;
map<point, int> hs;
point pt[110000], list[300000], now;
int n, m, cnt_list, fir;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
int vec[555][555], num_vec[555];
double ans[110000];
struct pp {
int id;
double x, y;
bool vis;
bool operator<(const pp &temp) const {
int f1, f2;
if (y > eps || (fabs(y) < eps && x < 0))
f1 = 1;
else if (y < -eps)
f1 = -1;
else
f1 = 0;
if (temp.y > eps || (fabs(temp.y) < eps && temp.x < 0))
f2 = 1;
else if (temp.y < -eps)
f2 = -1;
else
f2 = 0;
if (f1 != f2)
return f1 < f2;
return y * temp.x < x * temp.y - eps;
}
};
vector<pp> adj[255000];
pp awp;
bool cmp1(int id1, int id2) { return list[id1] < list[id2]; }
double l;
struct quyu {
vector<int> vp;
double area;
};
quyu qr[255555];
struct xxx {
int id, flag;
double x;
bool operator<(const xxx &temp) const {
if (fabs(x - temp.x) < eps)
return flag < temp.flag;
return x < temp.x;
}
};
xxx x[1000000];
int num_area, cnt_x;
void norm(double &theta) {
while (theta > pi - eps) theta -= 2 * pi;
while (theta < -pi + eps) theta += 2 * pi;
}
int binary(int left, int right, vector<pp> &adj, pp rf) {
int mid;
while (left <= right) {
mid = (left + right) >> 1;
if (adj[mid] < rf)
left = mid + 1;
else if (rf < adj[mid])
right = mid - 1;
else
return mid;
}
return -1;
}
void go(int uu, int vv) {
int i, j, s, p, q, id, ie;
double theta;
if (adj[uu][vv].vis)
return;
adj[uu][vv].vis = true;
qr[num_area].vp.push_back(uu);
id = adj[uu][vv].id;
pp rf;
rf.x = -adj[uu][vv].x;
rf.y = -adj[uu][vv].y;
ie = binary(0, adj[id].size() - 1, adj[id], rf);
go(id, (ie - 1 + adj[id].size()) % adj[id].size());
}
int main() {
scanf("%d%d%lf", &n, &m, &l);
int i, j, s, p, q, u, v;
for (i = 0; i < n; i++) scanf("%lf%lf%lf", &a[i], &b[i], &c[i]);
for (i = n; i < n + 4; i++) {
a[i] = dx[i - n];
b[i] = dy[i - n];
c[i] = l;
}
n += 4;
cnt_list = 0;
hs.clear();
for (i = 0; i < n; i++) {
num_vec[i] = 0;
for (j = 0; j < n; j++) {
if (i == j)
continue;
double aa, bb;
aa = (a[i] * b[j] - b[i] * a[j]);
bb = (-c[i] * b[j] + b[i] * c[j]);
if (fabs(aa) < eps)
continue;
now.x = bb / aa;
bb = (-c[j] * a[i] + a[j] * c[i]);
now.y = bb / aa;
if (now.x > l + eps || now.x < -l - eps || now.y > l + eps || now.y < -l - eps)
continue;
if (!hs.count(now)) {
list[cnt_list++] = now;
hs[now] = cnt_list - 1;
}
vec[i][num_vec[i]++] = hs[now];
}
sort(vec[i], vec[i] + num_vec[i], cmp1);
int nn = 0;
for (j = 0; j < num_vec[i]; j++) {
if (nn == 0 || vec[i][nn - 1] != vec[i][j])
vec[i][nn++] = vec[i][j];
}
num_vec[i] = nn;
for (j = 0; j < num_vec[i] - 1; j++) {
u = vec[i][j];
v = vec[i][j + 1];
awp.id = v;
awp.x = list[vec[i][j + 1]].x - list[vec[i][j]].x;
awp.y = list[vec[i][j + 1]].y - list[vec[i][j]].y;
adj[u].push_back(awp);
awp.id = u;
awp.x = list[vec[i][j]].x - list[vec[i][j + 1]].x;
awp.y = list[vec[i][j]].y - list[vec[i][j + 1]].y;
adj[v].push_back(awp);
}
}
for (i = 0; i < cnt_list; i++) sort(adj[i].begin(), adj[i].end());
num_area = 0;
for (i = 0; i < cnt_list; i++) {
for (j = 0; j < adj[i].size(); j++) adj[i][j].vis = false;
}
for (i = 0; i < cnt_list; i++) {
for (j = 0; j < adj[i].size(); j++) {
if (fabs(list[i].x - l) < eps || fabs(list[i].x + l) < eps || fabs(list[i].y - l) < eps ||
fabs(list[i].y + l) < eps)
continue;
if (!adj[i][j].vis) {
qr[num_area].vp.clear();
fir = i;
go(i, j);
num_area++;
}
}
}
cnt_ls = 0;
cnt_x = 0;
memset(num, 0, sizeof(num));
for (i = 0; i < num_area; i++) {
qr[i].area = 0;
if (qr[i].vp.size() >= 3) {
for (j = 1; j < qr[i].vp.size() - 1; j++) {
double x1, y1, x2, y2;
x1 = list[qr[i].vp[j]].x - list[qr[i].vp[0]].x;
y1 = list[qr[i].vp[j]].y - list[qr[i].vp[0]].y;
x2 = list[qr[i].vp[j + 1]].x - list[qr[i].vp[0]].x;
y2 = list[qr[i].vp[j + 1]].y - list[qr[i].vp[0]].y;
qr[i].area += 0.5 * (x1 * y2 - x2 * y1);
}
for (j = 0; j < qr[i].vp.size(); j++) {
an awp;
now.x = list[qr[i].vp[j]].x;
now.y = list[qr[i].vp[j]].y;
awp.l = qr[i].vp[j];
ls[cnt_ls].l = now;
now.x = list[qr[i].vp[(j + 1) % qr[i].vp.size()]].x;
now.y = list[qr[i].vp[(j + 1) % qr[i].vp.size()]].y;
ls[cnt_ls].r = now;
awp.r = qr[i].vp[(j + 1) % qr[i].vp.size()];
if (fabs(ls[cnt_ls].l.x - ls[cnt_ls].r.x) < eps)
continue;
if (ls[cnt_ls].r < ls[cnt_ls].l) {
swap(ls[cnt_ls].l, ls[cnt_ls].r);
swap(awp.l, awp.r);
}
int id;
long long state = 1LL * awp.l * cnt_list + awp.r;
int la = state % mod;
for (s = 0; s < num[la]; s++) {
if (fe[la][s] == state)
break;
}
if (s >= num[la]) // if(!fe.count(awp))
{
fe[la][num[la]] = state;
vl[la][num[la]++] = cnt_ls;
// fe[awp]=cnt_ls;
ls[cnt_ls].id = cnt_ls;
cnt_be[cnt_ls] = 0;
belong[cnt_ls][cnt_be[cnt_ls]++] = i;
cnt_ls++;
id = cnt_ls - 1;
} else {
id = vl[la][s];
// id=fe[awp];
belong[id][cnt_be[id]++] = i;
}
x[cnt_x].flag = 0;
x[cnt_x].x = ls[id].l.x;
x[cnt_x++].id = id;
x[cnt_x].flag = -1;
x[cnt_x].x = ls[id].r.x;
x[cnt_x++].id = id;
}
}
}
for (i = 0; i < m; i++) {
scanf("%lf%lf", &pt[i].x, &pt[i].y);
x[cnt_x].flag = 1;
x[cnt_x].id = i;
x[cnt_x++].x = pt[i].x;
}
sort(x, x + cnt_x);
ha.clear();
int nm = 0;
for (i = 0; i < cnt_x && nm < m; i++) {
if (x[i].flag == 0)
ha.insert(ls[x[i].id]);
else if (x[i].flag < 0)
ha.erase(ls[x[i].id]);
else {
nm++;
line bwp;
bwp.l = bwp.r = pt[x[i].id];
it = ha.lower_bound(bwp);
int bs[2], as[2], cnt_bs = cnt_be[it->id], cnt_as = 0;
for (j = 0; j < cnt_bs; j++) bs[j] = belong[it->id][j];
it--;
cnt_as = cnt_be[it->id];
for (j = 0; j < cnt_as; j++) as[j] = belong[it->id][j];
int ch = -1;
for (j = 0; j < cnt_bs; j++) {
for (s = 0; s < cnt_as; s++) {
if (bs[j] == as[s])
ch = as[s];
}
}
ans[x[i].id] = qr[ch].area;
}
}
for (i = 0; i < m; i++) printf("%.2f\n", ans[i]);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 240ms, 内存消耗: 7644K, 提交时间: 2019-01-07 17:59:44
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1e-7
bool same(double a,double b)
{
return (a-b>-eps && a-b<eps);
}
int n,m,t;
double x,y,z;
double L;
double ans[100010];
struct point{double x,y;};
struct et{point s;int id;} q[100010];
struct line
{
double A,B,C,k;
void create(double a,double b,double c)
{
A=a,B=b,C=c;
if (same(b,0)) k=1e50;else k=-a/b;
}
} l[510];
struct it{int l1,l2;point c;} c[260000];
bool operator <(line a,line b)//按照斜率对直线进行排序
{
if (same(a.k,b.k))
{
if (!same(a.B,0)) return a.C/a.B<b.C/b.B;
return a.C/a.A>b.C/b.A;
}
return a.k<b.k;
}
bool operator <(point a,point b)//按照x坐标对点进行排序
{
if (same(a.x,b.x)) return a.y<b.y;
return a.x<b.x;
}
bool operator <(et a,et b)
{
return a.s<b.s;
}
bool operator <(it a,it b)//对直线的交点进行排序
{
if (same(a.c.x,b.c.x) && same(a.c.y,b.c.y))
{
if (a.l1==b.l1) return a.l2<b.l2;
return a.l1<b.l1;
}
return a.c<b.c;
}
point cp(line a,line b)//求两条直线的交点
{
point ret;
ret.y=(b.C*a.A-a.C*b.A)/(a.B*b.A-a.A*b.B);
if (!same(a.A,0)) ret.x=-(ret.y*a.B+a.C)/a.A;
else ret.x=-(ret.y*b.B+b.C)/b.A;
return ret;
}
double cross(point a,point b)//计算叉积
{
return a.x*b.y-a.y*b.x;
}
double count(line a,point p)
{
return a.A*p.x+a.B*p.y+a.C;
}
void init()
{
l[n].create(-1,0,L);
l[n+1].create(-1,0,-L);
l[n+2].create(0,1,-L);
l[n+3].create(0,1,L);
n+=4;
sort(l,l+n);
t=0;
//计算直线的交点
for (int i=0;i<n;i++)
for (int j=i+1;j<n;j++)
if (!same(l[i].k,l[j].k))
{
c[t].l1=i,c[t].l2=j,c[t].c=cp(l[i],l[j]);
t++;
}
sort(q,q+m);
sort(c,c+t);
}
int xl[510],fd[510];
double s[510];
vector<int> que[510];
point last[510];
int bs(point p)//二分点的位置
{
int L=0,R=n,mid;
while (L<R)
{
mid=(L+R)/2;
if (count(l[xl[mid]],p)>0) R=mid;else L=mid+1;
}
return L;
}
void updata(int x)//x区域的面积计算完毕
{
for (int i=0;i<que[x].size();i++) ans[que[x][i]]=s[x];
s[x]=0;
que[x].clear();
}
void solve()
{
int j=0;
for (int i=0;i<n;i++) xl[i]=i,fd[i]=i;
for (int i=0;i<t;i++)
{
if (i==51)
{
j++;
j--;
}
while (q[j].s<c[i].c && j<m)
{
int x=bs(q[j].s);//二分确定点在第x个区域
que[x].push_back(q[j].id);//将第j个点加入第x区域的队列等待计算
j++;
}
int a=fd[c[i].l1],b=fd[c[i].l2];
double xa=cross(c[i].c,last[a]),xb=cross(last[b],c[i].c);
if (a+1!=b) printf("wa on %d\n",i);
s[b]-=xa+xb;
updata(b);
s[a]+=xa;
s[b+1]+=xb;
last[a]=last[b]=c[i].c;
swap(xl[a],xl[b]);
fd[xl[a]]=a;
fd[xl[b]]=b;
}
}
int main()
{
scanf("%d%d%lf",&n,&m,&L);
for (int i=0;i<n;i++)
{
scanf("%lf%lf%lf",&x,&y,&z);
if (same(y,0))
{
if (x>0) x=-x,z=-z;
}
else if (y<0) x=-x,y=-y,z=-z;
l[i].create(x,y,z);
}
for (int i=0;i<m;i++) scanf("%lf%lf",&q[i].s.x,&q[i].s.y);
for (int i=0;i<m;i++) q[i].id=i;
init();
solve();
for (int i=0;i<m;i++) printf("%.2lf\n",ans[i]/(-2));
return 0;
}