BZOJ1818 [Cqoi2010]内部白点 扫描线/线段求交

毫无头绪。。hint了一波瞄到了用扫描线做线段求交

想了想开始码。。过样例之后谜之wa

估计是加line的时候没把点做第二维排序，line不是一段一段进去的，加上就过了

//#include<bits/stdc++.h>  
#pragma comment(linker, "/STACK:1024000000,1024000000")   
#include<stdio.h>  
#include<algorithm>  
#include<queue>  
#include<string.h>  
#include<iostream>  
#include<math.h>  
#include<set>  
#include<map>  
#include<vector>  
#include<iomanip>  
using namespace std;  
#define ll long long  
#define pb push_back  
#define FOR(a) for(int i=1;i<=a;i++)  
const int inf=0x3f3f3f3f;  
 
const int maxn=2e5+5;    
 
int n,hash[maxn<<1];

struct dot{int x,y;}a[maxn];
bool cmp1(dot a,dot b){if(a.x==b.x){return a.y<b.y;}return a.x<b.x;}
bool cmp2(dot a,dot b){if(a.y==b.y){return a.x<b.x;}return a.y<b.y;}

struct Line{int x1,x2,y,kind;}line[maxn<<1];	//-1竖出1竖入，0横
bool cmp(Line a,Line b){
	if(a.y==b.y)return a.kind<b.kind;
	return a.y<b.y;
}

int sum[maxn<<2];
void pushup(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}
void update(int a,int b,int c,int l,int r,int rt){
	if(l==r){sum[rt]+=c;return;}
	int m=l+r>>1;
	if(a<=m)update(a,b,c,l,m,rt<<1);
	else update(a,b,c,m+1,r,rt<<1|1);
	pushup(rt);
}
int query(int a,int b,int l,int r,int rt){
	if(a<=l&&b>=r)return sum[rt];
	int m=l+r>>1;
	int ret=0;
	if(a<=m)ret+=query(a,b,l,m,rt<<1);
	if(b> m)ret+=query(a,b,m+1,r,rt<<1|1);
	return ret;
}

int main(){
	scanf("%d",&n);
	for(int i=1,x,y;i<=n;i++){
		scanf("%d%d",&x,&y);
		a[i]=(dot){x,y};
		hash[i]=a[i].x;
	}
	sort(hash+1,hash+1+n);
	int num=1;
	for(int i=2;i<=n;i++){
		if(hash[i]!=hash[i-1])hash[++num]=hash[i];
	}

	int tot=0;
	sort(a+1,a+1+n,cmp1);
	for(int i=2;i<=n;i++){
		if(a[i].x==a[i-1].x){
			int y1=min(a[i].y,a[i-1].y);
			int y2=max(a[i].y,a[i-1].y);
			line[++tot]=(Line){a[i].x,a[i].x,y1,1};
			line[++tot]=(Line){a[i].x,a[i].x,y2,-1};
		}
	}
	sort(a+1,a+1+n,cmp2);
	for(int i=2;i<=n;i++){
		if(a[i].y==a[i-1].y){
			int x1=min(a[i].x,a[i-1].x);
			int x2=max(a[i].x,a[i-1].x);
			line[++tot]=(Line){x1,x2,a[i].y,0};
		}
	}
	sort(line+1,line+1+tot,cmp);
	int ans=0;
	for(int i=1;i<=tot;i++){
		//cout<<i<<" "<<sum[1]<<endl;
		Line now=line[i];

		if(now.kind!=0){
			int l=lower_bound(hash+1,hash+1+num,now.x1)-hash;
			if(now.kind==1)update(l,l,1,1,num,1);
			else update(l,l,-1,1,num,1);

		}else{
			int l=lower_bound(hash+1,hash+1+num,now.x1)-hash;
			int r=lower_bound(hash+1,hash+1+num,now.x2)-hash;

			if(r==l+1)continue;

			ans+=query(l+1,r-1,1,num,1);
		}
		//cout<<i<<" "<<query(2,2,1,num,1)<<endl;
	}
	printf("%d
",ans+n);
}