POJ3109 Inner Vertices

すごくJOIに出そうな問題。点がN個与えられて、縦方向でも横方向でもある2つの点に挟まれているところが新たに点になる。最終的な点の数を求めよ。
座標圧縮してBITに持っておいたりすると通る。初めから十字になっているところを最初にひいている。
3K書いたのは結構久しぶりな気がする。

#include<stdio.h>
#include "stdafx.h"
#include<vector>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pll;
typedef pair<pair<int,int>,pll>pi4;
ll bit[131072];
void add(int a,ll b)
{
	for(;;)
	{
		if(a>131072)
		{
			break;
		}
		bit[a]+=b;
		a+=a&-a;
	}
}
ll sum(int a)
{
	ll ret=0;
	for(;;)
	{
		if(a==0)
		{
			break;
		}
		ret+=bit[a];
		a-=a&-a;
	}
	return ret;
}
int main()
{
	int num;
	scanf("%d",&num);
	vector<pll>tat;
	vector<pll>yok;
	ll ret=0;
	for(int i=0;i<num;i++)
	{
		ll za,zb;
		scanf("%lld%lld",&za,&zb);
		tat.push_back(make_pair(za,zb));
		yok.push_back(make_pair(zb,za));
	}
	sort(tat.begin(),tat.end());
	sort(yok.begin(),yok.end());
	for(int i=1;i<num-1;i++)
	{
		int low=lower_bound(yok.begin(),yok.end(),make_pair(tat[i].second,tat[i].first))-yok.begin();
		if(low!=0&&low!=num-1)
		{
			if(tat[i].first==tat[i-1].first&&tat[i].first==tat[i+1].first&&yok[low].first==yok[low-1].first&&yok[low].first==yok[low+1].first)
			{
				ret--;
			}
		}
	}
	vector<int>zt,zy;
	ll now=-100000000000000LL;\
	for(int i=0;i<num;i++)
	{
		if(now!=tat[i].first)
		{
			zt.push_back(tat[i].first);
			now=tat[i].first;
		}
	}
	now=-100000000000000LL;
	for(int i=0;i<num;i++)
	{
		if(now!=yok[i].first)
		{
			zy.push_back(yok[i].first);
			now=yok[i].first;
		}
	}
	for(int i=0;i<num;i++)
	{
		int low1=lower_bound(zt.begin(),zt.end(),tat[i].first)-zt.begin();
		int low2=lower_bound(zy.begin(),zy.end(),tat[i].second)-zy.begin();
		tat[i]=make_pair(low1,low2);
	}
	for(int i=0;i<num;i++)
	{
		int low1=lower_bound(zt.begin(),zt.end(),yok[i].second)-zt.begin();
		int low2=lower_bound(zy.begin(),zy.end(),yok[i].first)-zy.begin();
		yok[i]=make_pair(low2,low1);
	}
	vector<pi4>vec;
	for(ll i=0;i<zt.size();i++)
	{
		ll low=lower_bound(tat.begin(),tat.end(),make_pair(i,-10000000000000LL))-tat.begin();
		ll upp=upper_bound(tat.begin(),tat.end(),make_pair(i,100000000000000LL))-tat.begin();
		if(upp-low>1)
		{
			vec.push_back(make_pair(make_pair(tat[upp-1].second,-1),make_pair(-1,i)));
			vec.push_back(make_pair(make_pair(tat[low].second,1),make_pair(-1,i)));
		}
	}
	for(ll i=0;i<zy.size();i++)
	{
		ll low=lower_bound(yok.begin(),yok.end(),make_pair(i,-10000000000000LL))-yok.begin();
		ll upp=upper_bound(yok.begin(),yok.end(),make_pair(i,10000000000000LL))-yok.begin();
		if(upp-low>1)
		{
			vec.push_back(make_pair(make_pair(i,0),make_pair(yok[low].second+1,yok[upp-1].second-1)));
		}
	}
	sort(vec.begin(),vec.end());
	for(int i=0;i<vec.size();i++)
	{
		//printf("%d %d %lld %lld\n",vec[i].first.first,vec[i].first.second,vec[i].second.first,vec[i].second.second);
		if(vec[i].second.first==-1)
		{
			if(vec[i].first.second==-1)
			{
				add(vec[i].second.second+1,-1);
			}
			else
			{
				add(vec[i].second.second+1,1);
			}
		}
		else
		{
			ret+=sum(vec[i].second.second+1)-sum(vec[i].second.first);
		}
	}
	printf("%lld\n",ret+num);
}