HDU - 5862 Counting Intersections (스캐닝 라인 응용)
4901 단어 데이터 구조
Problem Description
Given some segments which are paralleled to the coordinate axis. You need to count the number of their intersection. The input data guarantee that no two segments share the same endpoint, no covered segments, and no segments with length 0.
Input
The first line contains an integer T, indicates the number of test case. The first line of each test case contains a number n(1<=n<=100000), the number of segments. Next n lines, each with for integers, x1, y1, x2, y2, means the two endpoints of a segment. The absolute value of the coordinate is no larger than 1e9.
Output
For each test case, output one line, the number of intersection.
Sample Input
2 4 1 0 1 3 2 0 2 3 0 1 3 1 0 2 3 2 4 0 0 2 0 3 0 3 2 3 3 1 3 0 3 0 2
Sample Output
4 0
题意:给你很多条平行于坐标轴的线段,然后求交点的个数。
思路:把平行于x轴的线段看成两个点,进点权值是+1,而出点权值为-1,把平行y轴的线,看作区间查询,注意:
入点和查询在同一个位置,先更新入点,出点和查询在同一个位置,那就先查询。当然首先得离散化y坐标~
代码:
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
const int maxn = 1e5 + 10;
struct node
{
int si,sj,pi,pj,w;
node(){}
node(int a,int b,int c,int d,int e)
{si = a; sj = b; pi = c; pj = d; w = e;}
}line[maxn << 1];
int yid[maxn << 1];
int ynum,num,t,n,m;
ll val[maxn << 4];
void init()
{
num = 0; ynum = 1;
memset(val,0,sizeof(val));
}
int getid(int x)
{
return lower_bound(yid + 1,yid + 1 + ynum , x) - yid;
}
bool cmp(node a,node b)
{
if(a.si == b.si)
{
return a.w > b.w;
}
return a.si < b.si;
}
void updata(int id,int l,int r,int u,int v)
{
//cout << l <>1;
if(u <= mid) updata(id << 1, l , mid, u, v);
else updata(id<<1|1, mid + 1, r, u, v);
val[id] = val[id<<1] + val[id<<1|1];
}
ll query(int id,int l,int r,int ql,int qr)
{
if(r < ql || l > qr) return 0;
if(l >= ql && r <= qr) return val[id];
int mid = l+r>>1;
ll ans = 0;
if(ql <= mid) ans += query(id<<1, l , mid, ql , qr);
if(qr > mid) ans += query(id<<1|1,mid+1,r,ql,qr);
return ans;
}
int main()
{
//freopen("D:\\in.txt","r",stdin);
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
init();
int anum = 0,bnum = 0;
for(int i = 0; i < n; i++)
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
yid[ynum++] = b, yid[ynum++] = d;
if(b == d)
{
anum++;
if(a > c) swap(a,c);
line[num++] = node(a,b,0,0, 1);
line[num++] = node(c,d,0,0,-1);
}
else
{
bnum++;
line[num++] = node(a,b,c,d,0);
}
}
if(anum == 0 || bnum == 0)
{
printf("0
");
continue;
}
sort(line, line + num, cmp);
//
sort(yid + 1 , yid + 1 + ynum);
ynum = unique(yid + 1,yid + 1 + ynum) - yid;
ll ans = 0;
for(int i = 0; i < num; i++)
{
int w = line[i].w;
if(w != 0)
{
int id = getid(line[i].sj);
updata(1,1,ynum-1,id,w);
}
else
{
int l = getid(line[i].sj), r = getid(line[i].pj);
if(l > r) swap(l,r);
ll temp = query(1,1,ynum-1,l,r);
ans += temp;
}
}
cout << ans << endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.