Submission #126358

#	Time	Username	Problem	Language	Result	Execution time	Memory
126358		youngyojun	Demarcation (BOI14_demarcation)	C++11	100 / 100	211 ms	30328 KiB

demarcation

#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>

#define _N 101010
#define EXIT {printf("NO\n");return 0;}
#define labs(a) ((a)>0?(a):-(a))

using namespace std;

typedef long long ll;

struct pl{ll f,s;};
pl mp(ll _f,ll _s){pl _p;_p.f=_f,_p.s=_s;return _p;}
pl P[_N],Div[_N]; // point
ll L[_N],n,ap,bp,cp,xp,yp; // perimeter
ll Dx[_N],Dy[_N]; // direction
pl A[_N],B[_N],_A[_N],_B[_N];

pl Cs[_N],Ce[_N];
map <ll,ll> X,Y;
ll Tx[_N],Ty[_N];
bool Ox[_N],Oy[_N];
vector <ll> Vlx[_N],Vly[_N],Vcx[_N],Vcy[_N];

ll Add(ll* Arr,ll p,ll val)
{
	while(p<=n){
		Arr[p] += val;
		p += (p&-p);
	}

	return 0;
}

ll Range(ll* Arr,ll s,ll e)
{
	if(s>e) return 0;

	ll ret=0;
	s--;
	while(s){
		ret -= Arr[s];
		s -= (s&-s);
	}
	while(e){
		ret += Arr[e];
		e -= (e&-e);
	}

	return ret;
}

ll Check(pl s,pl e)
{
	int x1,x2,y1,y2,_a,_b,i,j;

	x1 = P[s.f].f+Dx[s.f]*s.s, y1 = P[s.f].s+Dy[s.f]*s.s;
	x2 = P[e.f].f+Dx[e.f]*e.s, y2 = P[e.f].s+Dy[e.f]*e.s;
	
	_A[_a++] = mp(x1,y1);
	for(i=s.f+1;i<=e.f;i++) _A[_a++] = mp(P[i].f,P[i].s);
	_A[_a++] = mp(x2,y2);
	for(ap=i=0;i<_a;i++){
		if((_A[(i+_a-1)%_a].f!=_A[i].f||_A[i].f!=_A[(i+1)%_a].f)
			&& (_A[(i+_a-1)%_a].s!=_A[i].s||_A[i].s!=_A[(i+1)%_a].s)) A[ap++] = _A[i];
	}
	_B[_b++] = mp(x2,y2);
	for(i=(e.f+1)%n;i!=s.f+1;i=(i+1)%n) _B[_b++] = mp(P[i].f,P[i].s);
	_B[_b++] = mp(x1,y1);
	for(bp=i=0;i<_b;i++){
		if((_B[(i+_b-1)%_b].f!=_B[i].f||_B[i].f!=_B[(i+1)%_b].f)
			&& (_B[(i+_b-1)%_b].s!=_B[i].s||_B[i].s!=_B[(i+1)%_b].s)) B[bp++] = _B[i];
	}
	
	if(ap != bp) return 0;

	for(i=_a=0;i<ap;i++) if(A[i].f < A[_a].f || (A[i].f == A[_a].f && A[i].s < A[_a].s)) _a=i;

	for(j=0;j<8;j++){
		for(i=_b=0;i<bp;i++){
			swap(B[i].f,B[i].s);
			if(j!=4) B[i].f = -B[i].f;
			if(B[i].f < B[_b].f || (B[i].f == B[_b].f && B[i].s < B[_b].s)) _b=i;
		}
		for(i=0;i<bp;i++){
			if((A[(_a+i)%ap].f-A[_a].f != B[(_b+i)%bp].f-B[_b].f) || 
				(A[(_a+i)%ap].s-A[_a].s != B[(_b+i)%bp].s-B[_b].s)) break;
		}
		if(i==bp){
			printf("%lld %lld %lld %lld\n",x1,y1,x2,y2);
			return 1;
		}
	}

	for(i=0;i<bp/2;i++) swap(B[i],B[bp-i-1]);

	for(j=0;j<8;j++){
		for(i=_b=0;i<bp;i++){
			swap(B[i].f,B[i].s);
			if(j!=4) B[i].f = -B[i].f;
			if(B[i].f < B[_b].f || (B[i].f == B[_b].f && B[i].s < B[_b].s)) _b=i;
		}
		for(i=0;i<bp;i++){
			if((A[(_a+i)%ap].f-A[_a].f != B[(_b+i)%bp].f-B[_b].f) || 
				(A[(_a+i)%ap].s-A[_a].s != B[(_b+i)%bp].s-B[_b].s)) break;
		}
		if(i==bp){
			printf("%lld %lld %lld %lld\n",x1,y1,x2,y2);
			return 1;
		}
	}

	return 0;
}

int main()
{
	scanf("%d",&n);

	ll i,j,k,a,b,c,d,l1,l2,x1,y1,x2,y2;
	pl s,e;

	for(i=0;i<n;i++){
		scanf("%lld%lld",&P[i].f,&P[i].s);
		X[P[i].f] ++, Y[P[i].s] ++;

		if(i){
			L[i] = L[i-1] + labs(P[i].f-P[i-1].f+P[i].s-P[i-1].s);
			if(P[i-1].f == P[i].f) Dy[i-1] = P[i-1].s<P[i].s?1:-1;
			else Dx[i-1] = P[i-1].f<P[i].f?1:-1;
		}
	}
	L[n] = L[n-1] + labs(P[0].f-P[n-1].f+P[0].s-P[n-1].s);
	if(P[n-1].f == P[0].f) Dy[n-1] = P[n-1].s<P[0].s?1:-1;
	else Dx[n-1] = P[n-1].f<P[0].f?1:-1;

	if(L[n]%2) EXIT

	for(e.f=0;L[e.f]<=L[n]/2;e.f++);
	e.f--, e.s = L[n]/2-L[e.f];

	for(s=mp(0,0);e.f<n;){
		a = L[s.f+1]-(L[s.f]+s.s), b = L[e.f+1]-(L[e.f]+e.s);

		if(Dx[s.f]*Dx[e.f]<0){
			k = labs((P[s.f].f+Dx[s.f]*s.s)-(P[e.f].f+Dx[e.f]*e.s));
			if(k%2 == 0 && k/2<=a && k/2<=b){
				s.s += k/2, e.s += k/2;
				x1 = Dx[s.f]*s.s;
				x2 = Dx[e.f]*e.s;
				if(P[s.f].f+x1 == P[e.f].f+x2){
					Cs[cp] = s, Ce[cp++] = e;
					X[P[s.f].f+x1]++, Y[P[s.f].s]++, Y[P[e.f].s]++;
				}
				s.s -= k/2, e.s -= k/2;
			}
		}
		else if(Dy[s.f]*Dy[e.f]<0){
			k = labs((P[s.f].s+Dy[s.f]*s.s)-(P[e.f].s+Dy[e.f]*e.s));
			if(k%2 == 0 && k/2<=a && k/2<=b){
				s.s += k/2, e.s += k/2;
				y1 = Dy[s.f]*s.s;
				y2 = Dy[e.f]*e.s;
				if(P[s.f].s+y1 == P[e.f].s+y2){
					Cs[cp] = s, Ce[cp++] = e;
					X[P[s.f].f]++, X[P[e.f].f]++, Y[P[s.f].s+y1] ++;
				}
				s.s -= k/2, e.s -= k/2;
			}
		}

		s.s += min(a,b), e.s += min(a,b);

		if(a==0) s.f++, s.s=0;
		else if(b==0){
			e.f++, e.s=0;
			if(s.s == 0) s.f--, s.s = L[s.f+1]-L[s.f];
		}
	}

	// faster...

	for(auto t=X.begin(); t!=X.end(); t++,xp++) t->second = xp+1;
	for(auto t=Y.begin(); t!=Y.end(); t++,yp++) t->second = yp+1;

	for(i=0;i<n;i++){
		if(P[i].s == P[(i+1)%n].s){
			Vlx[X[P[i].f]].push_back(i);
			Vlx[X[P[(i+1)%n].f]].push_back(i);
		}
		else{
			Vly[Y[P[i].s]].push_back(i);
			Vly[Y[P[(i+1)%n].s]].push_back(i);
		}
	}
	for(i=0;i<cp;i++){
		s = Cs[i], e = Ce[i];
		x1 = P[s.f].f+Dx[s.f]*s.s, y1 = P[s.f].s+Dy[s.f]*s.s;
		x2 = P[e.f].f+Dx[e.f]*e.s, y2 = P[e.f].s+Dy[e.f]*e.s;
		if(x1 == x2) Vcx[X[x1]].push_back(i);
		else Vcy[Y[y1]].push_back(i);
	}

	for(i=1;i<=xp;i++){
		for(j=0;j<Vlx[i].size();j++){
			if(!Ox[Vlx[i][j]]) Add(Tx,Y[P[Vlx[i][j]].s],1);
		}
		for(j=0;j<Vcx[i].size();j++){
			s = Cs[Vcx[i][j]], e = Ce[Vcx[i][j]];
			y1 = P[s.f].s+Dy[s.f]*s.s, y2 = P[e.f].s+Dy[e.f]*e.s;
			if(y1>y2) swap(y1,y2);
			if(Range(Tx,Y[y1]+1,Y[y2]-1) == 0 && Check(s,e)) return 0;
		}
		for(j=0;j<Vlx[i].size();j++){
			if(Ox[Vlx[i][j]]) Add(Tx,Y[P[Vlx[i][j]].s],-1);
			else Ox[Vlx[i][j]] = 1;
		}
	}

	for(i=1;i<=yp;i++){
		for(j=0;j<Vly[i].size();j++){
			if(!Oy[Vly[i][j]]) Add(Ty,X[P[Vly[i][j]].f],1);
		}
		for(j=0;j<Vcy[i].size();j++){
			s = Cs[Vcy[i][j]], e = Ce[Vcy[i][j]];
			x1 = P[s.f].f+Dx[s.f]*s.s, x2 = P[e.f].f+Dx[e.f]*e.s;
			if(x1>x2) swap(x1,x2);
			if(Range(Ty,X[x1]+1,X[x2]-1) == 0 && Check(s,e)) return 0;
		}
		for(j=0;j<Vly[i].size();j++){
			if(Oy[Vly[i][j]]) Add(Ty,X[P[Vly[i][j]].f],-1);
			else Oy[Vly[i][j]] = 1;
		}
	}

	EXIT
}

Compilation message (stderr)

demarcation.cpp: In function 'll Check(pl, pl)':
demarcation.cpp:92:46: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
    printf("%lld %lld %lld %lld\n",x1,y1,x2,y2);
                                              ^
demarcation.cpp:92:46: warning: format '%lld' expects argument of type 'long long int', but argument 3 has type 'int' [-Wformat=]
demarcation.cpp:92:46: warning: format '%lld' expects argument of type 'long long int', but argument 4 has type 'int' [-Wformat=]
demarcation.cpp:92:46: warning: format '%lld' expects argument of type 'long long int', but argument 5 has type 'int' [-Wformat=]
demarcation.cpp:110:46: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
    printf("%lld %lld %lld %lld\n",x1,y1,x2,y2);
                                              ^
demarcation.cpp:110:46: warning: format '%lld' expects argument of type 'long long int', but argument 3 has type 'int' [-Wformat=]
demarcation.cpp:110:46: warning: format '%lld' expects argument of type 'long long int', but argument 4 has type 'int' [-Wformat=]
demarcation.cpp:110:46: warning: format '%lld' expects argument of type 'long long int', but argument 5 has type 'int' [-Wformat=]
demarcation.cpp: In function 'int main()':
demarcation.cpp:120:15: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
  scanf("%d",&n);
             ~~^
demarcation.cpp:207:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<Vlx[i].size();j++){
           ~^~~~~~~~~~~~~~
demarcation.cpp:210:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<Vcx[i].size();j++){
           ~^~~~~~~~~~~~~~
demarcation.cpp:216:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<Vlx[i].size();j++){
           ~^~~~~~~~~~~~~~
demarcation.cpp:223:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<Vly[i].size();j++){
           ~^~~~~~~~~~~~~~
demarcation.cpp:226:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<Vcy[i].size();j++){
           ~^~~~~~~~~~~~~~
demarcation.cpp:232:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<Vly[i].size();j++){
           ~^~~~~~~~~~~~~~
demarcation.cpp:122:15: warning: unused variable 'c' [-Wunused-variable]
  ll i,j,k,a,b,c,d,l1,l2,x1,y1,x2,y2;
               ^
demarcation.cpp:122:17: warning: unused variable 'd' [-Wunused-variable]
  ll i,j,k,a,b,c,d,l1,l2,x1,y1,x2,y2;
                 ^
demarcation.cpp:122:19: warning: unused variable 'l1' [-Wunused-variable]
  ll i,j,k,a,b,c,d,l1,l2,x1,y1,x2,y2;
                   ^~
demarcation.cpp:122:22: warning: unused variable 'l2' [-Wunused-variable]
  ll i,j,k,a,b,c,d,l1,l2,x1,y1,x2,y2;
                      ^~
demarcation.cpp:120:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
demarcation.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&P[i].f,&P[i].s);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
demarcation.cpp: In function 'll Check(pl, pl)':
demarcation.cpp:62:7: warning: '_a' is used uninitialized in this function [-Wuninitialized]
  _A[_a++] = mp(x1,y1);
     ~~^~
demarcation.cpp:69:7: warning: '_b' is used uninitialized in this function [-Wuninitialized]
  _B[_b++] = mp(x2,y2);
     ~~^~

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 23 / 23
• Subtask 4: 50 / 50