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); }