Submission #263462

#	Time	Username	Problem	Language	Result	Execution time	Memory
263462		TadijaSebez	Demarcation (BOI14_demarcation)	C++11	100 / 100	155 ms	22276 KiB

demarcation

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
struct pt{
	ll x,y;
	pt(ll a=0,ll b=0):x(a),y(b){}
	bool operator == (pt b)const{return mp(x,y)==mp(b.x,b.y);}
	bool operator != (pt b)const{return mp(x,y)!=mp(b.x,b.y);}
	bool operator < (pt b)const{return mp(x,y)<mp(b.x,b.y);}
};
pt operator - (pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
pt operator -= (pt&a,pt b){return a=a-b;}
pt operator + (pt a,pt b){return pt(a.x+b.x,a.y+b.y);}
pt operator += (pt&a,pt b){return a=a+b;}
bool eq(vector<pt> a,vector<pt> b){
	if(a.size()!=b.size())return 0;
	for(int i=0;i<a.size();i++)if(a[i]!=b[i])return 0;
	return 1;
}
void norm(vector<pt>&a){
	int mn=0;
	for(int i=0;i<a.size();i++)if(a[i]<a[mn])mn=i;
	vector<pt> tmp;
	for(int i=0;i<a.size();i++)tmp.pb(a[(mn+i)%a.size()]);
	a=tmp;
	if(a[1].x==a[0].x)reverse(a.begin()+1,a.end());
	for(int i=1;i<a.size();i++)a[i]-=a[0];
	a[0]=pt(0,0);
}
void rotate(vector<pt>&a){
	for(pt&p:a)p=pt(-p.y,p.x);
}
void mirror(vector<pt>&a){
	for(pt&p:a)p=pt(-p.x,p.y);
}
bool on_line(pt a,pt b,pt c){
	return (a.x==b.x&&a.x==c.x)||(a.y==b.y&&a.y==c.y);
}
void pop(vector<pt>&a){
	while(a.size()>3&&on_line(a.back(),a[0],a[1]))a.erase(a.begin());
	while(a.size()>3&&on_line(a[0],a.back(),a[(int)a.size()-2]))a.pop_back();
	while(a.size()>3&&on_line(a[(int)a.size()-3],a[(int)a.size()-2],a.back()))a.erase(a.end()-2);
}
pt min_pt(vector<pt> a){
	pt ans=a[0];
	for(pt p:a)ans=min(ans,p);
	return ans;
}
bool Check(vector<pt> a,vector<pt> b){
	if(a.size()!=b.size())return 0;
	norm(a);
	for(int i=0;i<2;i++){
		for(int j=0;j<4;j++){
			norm(b);
			if(eq(a,b))return 1;
			rotate(b);
		}
		mirror(b);
	}
	return 0;
}
struct seg{
	pt a,b;
	seg(){}
	seg(pt x,pt y):a(x),b(y){}
	int type(){
		if(a.y==b.y)return a.x<b.x?-1:1;
		if(a.x==b.x)return a.y<b.y?2:3;
	}
	ll get(){
		return a.y*(a.x-b.x);
	}
	ll X(){return (a.x+b.x)/2;}
};
const int N=200050;
seg s[N];
ll sum[N],tme[N];
bool Solve(vector<pt> a,seg&ans){
	vector<pii> evs;
	for(int i=0;i<a.size();i++){
		int j=(i+1)%a.size();
		s[i+1]=seg(a[i],a[j]);
		evs.pb({min(a[i].y,a[j].y),-i-1});
		evs.pb({max(a[i].y,a[j].y),i+1});
	}
	for(int i=1;i<=a.size();i++)sum[i]=sum[i-1]+s[i].get();
	ll area=sum[a.size()];
	auto cmp=[&](int a,int b){return s[a].X()<s[b].X();};
	set<int,decltype(cmp)> all(cmp);
	auto cons=[&](int j,int i,ll tr,seg&ans){
		ll tl=tme[j];
		if(tl>tr)return 0;
		if(s[i].type()!=2||s[j].type()!=3)return 0;
		ll A=sum[j]+(j<i?sum[a.size()]-sum[i-1]:-sum[i-1]);
		ll dif=A-area/2;
		ll rng=s[i].a.x-s[j].a.x;
		if(dif%rng!=0)return 0;
		ll H=dif/rng;
		if(H&1)return 0;
		if(H>=tl&&H<=tr){
			pt o1(s[i].a.x,H),o2(s[j].a.x,H);
			vector<pt> p1,p2;
			for(int i1=i;i1!=j;i1=i1==a.size()?1:i1+1){
				p1.pb(s[i1].b);
			}
			if(p1.back()!=o2)p1.pb(o2);
			if(p1.front()!=o1)p1.pb(o1);
			for(int i2=j;i2!=i;i2=i2==a.size()?1:i2+1){
				p2.pb(s[i2].b);
			}
			if(p2.back()!=o1)p2.pb(o1);
			if(p2.front()!=o2)p2.pb(o2);
			pop(p1);pop(p2);
			if(Check(p1,p2)){
				ans=seg(o1,o2);
				return 1;
			}
		}
		return 0;
	};
	sort(evs.begin(),evs.end());
	for(auto e:evs){
		ll t=e.first;
		int i=abs(e.second);
		if(e.second<0){
			all.insert(i);
			auto it=all.find(i);
			if(it!=all.begin()&&next(it)!=all.end()){
				if(cons(*prev(it),*next(it),t-2,ans))
					return 1;
			}
			if(it!=all.begin()){
				tme[*prev(it)]=t;
			}
			if(next(it)!=all.end()){
				tme[i]=t;
			}
		}else{
			auto it=all.find(i);
			if(it!=all.begin()){
				if(cons(*prev(it),*it,t,ans))
					return 1;
			}
			if(next(it)!=all.end()){
				if(cons(*it,*next(it),t,ans))
					return 1;
			}
			if(it!=all.begin()&&next(it)!=all.end()){
				tme[*prev(it)]=t+2;
			}
			all.erase(it);
		}
	}
	return 0;
}
int main(){
	int n;
	scanf("%i",&n);
	vector<pt> a(n);
	for(pt&p:a)scanf("%lld %lld",&p.x,&p.y),p.x*=2,p.y*=2;
	pt add=min_pt(a);
	seg ans;
	norm(a);
	if(Solve(a,ans)){
		ans.a+=add;
		ans.b+=add;
		printf("%lld %lld %lld %lld\n",ans.a.x/2,ans.a.y/2,ans.b.x/2,ans.b.y/2);
		return 0;
	}
	rotate(a);
	pt add2=min_pt(a);
	norm(a);
	if(Solve(a,ans)){
		ans.a+=add2;
		ans.b+=add2;
		vector<pt> sol={ans.a,ans.b};
		for(int i=0;i<3;i++)rotate(sol);
		sol[0]+=add;
		sol[1]+=add;
		printf("%lld %lld %lld %lld\n",sol[0].x/2,sol[0].y/2,sol[1].x/2,sol[1].y/2);
		return 0;
	}
	printf("NO\n");
	return 0;
}

Compilation message (stderr)

demarcation.cpp: In function 'bool eq(std::vector<pt>, std::vector<pt>)':
demarcation.cpp:20:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=0;i<a.size();i++)if(a[i]!=b[i])return 0;
      |              ~^~~~~~~~~
demarcation.cpp: In function 'void norm(std::vector<pt>&)':
demarcation.cpp:25:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i=0;i<a.size();i++)if(a[i]<a[mn])mn=i;
      |              ~^~~~~~~~~
demarcation.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i=0;i<a.size();i++)tmp.pb(a[(mn+i)%a.size()]);
      |              ~^~~~~~~~~
demarcation.cpp:30:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i=1;i<a.size();i++)a[i]-=a[0];
      |              ~^~~~~~~~~
demarcation.cpp: In function 'bool Solve(std::vector<pt>, seg&)':
demarcation.cpp:83:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for(int i=0;i<a.size();i++){
      |              ~^~~~~~~~~
demarcation.cpp:89:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for(int i=1;i<=a.size();i++)sum[i]=sum[i-1]+s[i].get();
      |              ~^~~~~~~~~~
demarcation.cpp: In lambda function:
demarcation.cpp:106:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |    for(int i1=i;i1!=j;i1=i1==a.size()?1:i1+1){
      |                          ~~^~~~~~~~~~
demarcation.cpp:111:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |    for(int i2=j;i2!=i;i2=i2==a.size()?1:i2+1){
      |                          ~~^~~~~~~~~~
demarcation.cpp: In member function 'int seg::type()':
demarcation.cpp:72:2: warning: control reaches end of non-void function [-Wreturn-type]
   72 |  }
      |  ^
demarcation.cpp: In function 'int main()':
demarcation.cpp:161:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  161 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
demarcation.cpp:163:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  163 |  for(pt&p:a)scanf("%lld %lld",&p.x,&p.y),p.x*=2,p.y*=2;
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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