Submission #106908

#	Time	Username	Problem	Language	Result	Execution time	Memory
106908		wilwxk	Demarcation (BOI14_demarcation)	C++11	0 / 100	8 ms	640 KiB

demarcation

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct point {
	ll x, y;
	point operator-(point outro) {
		point novo;
		novo.x=x-outro.x;
		novo.y=y-outro.y;
		return novo;
	}
};

const int MAXN=1e5+5;
point p[MAXN];
int n;
ll tudo;
ll mnx, mny, mxx, mxy;

ll area(ll val, int k) {
	ll resp=0;
	for(int i=3; i<=n; i++) {
		point a=p[i]; point b=p[i-1];
		if(k==1) a.x=min(a.x, val), b.x=min(b.x, val);
		if(k==2) a.y=min(a.y, val), b.y=min(b.y, val);
		a=a-p[1]; b=b-p[1];
		resp+=(a.x*b.y)-(a.y*b.x);
	}
	// printf("area %lld %d > %lld\n", val, k, abs(resp)/2);
	return abs(resp)/2;
}

bool testa(ll corte, int k) {
	if(area(corte, k)!=tudo/2) return 0;
	multiset<ll> s, s2;
	// printf("testa corte=%lld k=%d\n", corte, k);
	ll ini=-1; ll fim=-1;
	ll ini2=-1; ll fim2=-1;

	//parte esquerda e direita
	if(k==1) {
		for(int i=1; i<=n; i++) {
			point cur=p[i]; point anter= i==1 ? p[n] : p[i-1];
			ll val=abs(cur.x-anter.x)+abs(cur.y-anter.y);
			// printf("%d: %lld // cmp (%lld %lld) <-> (%lld %lld)\n", i, val, cur.x, cur.y, anter.x, anter.y);

			if(anter.x==cur.x) {
				if(anter.x<corte) s.insert(val);
				if(anter.x>corte) s2.insert(val);
				continue;
			}

			if(corte<anter.x&&corte<cur.x) s2.insert(val);
			else if(corte>anter.x&&corte>cur.x) s.insert(val);
			else if(anter.x<=cur.x&&corte<=cur.x) s.insert(val-abs(cur.x-corte)), s2.insert(abs(cur.x-corte));
			else s.insert(abs(cur.x-corte)), s2.insert(val-abs(cur.x-corte));

			if((cur.x<=corte&&anter.x<=corte&&(cur.x==corte||anter.x==corte))||min(cur.x, anter.x)<corte&&max(cur.x, anter.x)>corte) {
				if(ini>=0&&fim==-1) s.insert(abs(cur.y-ini)), fim=cur.y;
				else if(ini==-1) ini=cur.y;
			}
			if((cur.x>=corte&&anter.x>=corte&&(cur.x==corte||anter.x==corte))||min(cur.x, anter.x)<corte&&max(cur.x, anter.x)>corte) {
				if(ini2>=0&&fim2==-1) s2.insert(abs(cur.y-ini2)), fim2=cur.y;
				else if(ini2==-1) ini2=cur.y;
			}

		}
	}

	//parte direita/superior
	if(k==2) {
		for(int i=1; i<=n; i++) {
			point cur=p[i]; point anter= i==1 ? p[n] : p[i-1];
			ll val=abs(cur.x-anter.x)+abs(cur.y-anter.y);
			// printf("%d: %lld // cmp (%lld %lld) <-> (%lld %lld)\n", i, val, cur.x, cur.y, anter.x, anter.y);

			if(anter.y==cur.y) {
				if(anter.y<corte) s.insert(val);
				if(anter.y>corte) s2.insert(val);
				continue;
			}

			if(corte<anter.y&&corte<cur.y) s2.insert(val);
			else if(corte>anter.y&&corte>cur.y) s.insert(val);
			else if(anter.y<=cur.y&&corte<=cur.y) s.insert(val-abs(cur.y-corte)), s2.insert(abs(cur.y-corte));
			else s.insert(abs(cur.y-corte)), s2.insert(val-abs(cur.y-corte));

			if((cur.y<=corte&&anter.y<=corte&&(cur.y==corte||anter.y==corte))||min(cur.y, anter.y)<corte&&max(cur.y, anter.y)>corte) {
				if(ini>=0&&fim==-1) s.insert(abs(cur.x-ini)), fim=cur.x;
				else if(fim==-1) ini=cur.x;
			}
			if((cur.y>=corte&&anter.y>=corte&&(cur.y==corte||anter.y==corte))||min(cur.y, anter.y)<corte&&max(cur.y, anter.y)>corte) {
				if(ini2>=0&&fim2==-1) s2.insert(abs(cur.x-ini2)), fim2=cur.x;
				else if(fim2==-1) ini2=cur.x;
			}
			// printf("  marcs %lld %lld\n", marc, marc2);

		}
	}
	// printf("///s: "); for(auto cur : s) printf("%lld ", cur); printf("\n");
	// printf("///s2: "); for(auto cur : s2) printf("%lld ", cur); printf("\n");

	s.erase(0); s2.erase(0);
	if(s==s2) {
		if(abs(fim-ini)>abs(ini2-fim2)) ini2=ini, fim2=fim;
		if(k==1) printf("%lld %lld %lld %lld\n", corte, ini2, corte, fim2);
		if(k==2) printf("%lld %lld %lld %lld\n", ini2, corte, fim2, corte);
		return 1;
	}
	return 0;
}

int main() {
	scanf("%d", &n);
	for(int i=1; i<=n; i++) {
		scanf("%lld %lld", &p[i].x, &p[i].y);
		mnx=min(mnx, p[i].x); mxx=max(mxx, p[i].x);
		mny=min(mny, p[i].y); mxy=max(mxy, p[i].y);
	}

	tudo=area(mxx, -1);
	// printf("area= %lld\n", tudo);

	// testa vertical
	int ind=mnx; for(int i=mxx; i>0; i/=2) while(ind+i<=mxx&&area(ind+i, 1)<=tudo/2) ind+=i; //printf("vert ind= %d > %lld\n", ind, area(ind, 1));
	if(testa(ind, 1)) return 0;

	// testa horizontal
	ind=mny; for(int i=mxy; i>0; i/=2) while(ind+i<=mxy&&area(ind+i, 2)<=tudo/2) ind+=i; //printf("horiz ind= %d > %lld\n", ind, area(ind, 2));
	if(testa(ind, 2)) return 0;

	printf("NO\n");
	
}

Compilation message (stderr)

demarcation.cpp: In function 'bool testa(ll, int)':
demarcation.cpp:59:96: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    if((cur.x<=corte&&anter.x<=corte&&(cur.x==corte||anter.x==corte))||min(cur.x, anter.x)<corte&&max(cur.x, anter.x)>corte) {
                                                                       ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
demarcation.cpp:63:96: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    if((cur.x>=corte&&anter.x>=corte&&(cur.x==corte||anter.x==corte))||min(cur.x, anter.x)<corte&&max(cur.x, anter.x)>corte) {
                                                                       ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
demarcation.cpp:89:96: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    if((cur.y<=corte&&anter.y<=corte&&(cur.y==corte||anter.y==corte))||min(cur.y, anter.y)<corte&&max(cur.y, anter.y)>corte) {
                                                                       ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
demarcation.cpp:93:96: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    if((cur.y>=corte&&anter.y>=corte&&(cur.y==corte||anter.y==corte))||min(cur.y, anter.y)<corte&&max(cur.y, anter.y)>corte) {
                                                                       ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
demarcation.cpp: In function 'int main()':
demarcation.cpp:115:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
demarcation.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &p[i].x, &p[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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