oj.uz

답안 #263078

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
263078 2020-08-13T12:48:39 Z TadijaSebez 경계 (BOI14_demarcation) C++11
0 / 100
 9 ms 7768 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
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);
	}
};
const int N=200050;
seg s[N];
ll sum[N];
bool Solve(vector<pt> a,seg&ans){
	for(int i=0;i<a.size();i++){
		int j=(i+1)%a.size();
		s[i+1]=seg(a[i],a[j]);
	}
	for(int i=1;i<=a.size();i++)sum[i]=sum[i-1]+s[i].get();
	int hal=a.size()/2;
	ll area=sum[a.size()];
	//printf("%lld\n",area);
	if(area&1)return 0;
	assert(area>0);
	for(int i=1;i<=a.size();i++)if(s[i].type()==2){
		for(int z=-3;z<=3;z++){
			int j=(i-1+hal+z+a.size())%a.size()+1;
			if(s[j].type()==3&&s[j].a.x<s[i].a.x){
				//printf("%i - %i\n",i,j);
				ll A=sum[j]+(j<i?sum[a.size()]-sum[i-1]:-sum[i-1]);
				//printf("A: %lld\n",A);
				ll dif=A-area/2;
				ll rng=s[i].a.x-s[j].a.x;
				//printf("dif:%lld rng:%lld\n",dif,rng);
				if(dif%rng!=0)continue;
				ll H=dif/rng;
				if(s[i].a.y<=H&&s[i].b.y>=H&&s[j].b.y<=H&&s[j].a.y>=H){
					//printf(":D H:%lld\n",H);
					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);
					//for(pt p:p1)printf("(%lld %lld) ",p.x,p.y);printf("\n");
					//for(pt p:p2)printf("(%lld %lld) ",p.x,p.y);printf("\n");
					if(Check(p1,p2)){
						ans=seg(o1,o2);
						return 1;
					}
				}
			}
		}
	}
	return 0;
}
int main(){
	int n;
	scanf("%i",&n);
	vector<pt> a(n);
	for(pt&p:a)scanf("%lld %lld",&p.x,&p.y);
	pt add=min_pt(a);
	seg ans;
	norm(a);
	//for(pt p:a)printf("(%lld %lld) ",p.x,p.y);printf("\n");
	if(Solve(a,ans)){
		ans.a+=add;
		ans.b+=add;
		printf("%lld %lld %lld %lld\n",ans.a.x,ans.a.y,ans.b.x,ans.b.y);
		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,sol[0].y,sol[1].x,sol[1].y);
		return 0;
	}
	printf("NO\n");
	return 0;
}

Compilation message

demarcation.cpp: In function 'bool eq(std::vector<pt>, std::vector<pt>)':
demarcation.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  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:24:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i=0;i<a.size();i++)if(a[i]<a[mn])mn=i;
      |              ~^~~~~~~~~
demarcation.cpp:26:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i=0;i<a.size();i++)tmp.pb(a[(mn+i)%a.size()]);
      |              ~^~~~~~~~~
demarcation.cpp:29:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i=1;i<a.size();i++)a[i]-=a[0];
      |              ~^~~~~~~~~
demarcation.cpp: In function 'bool Solve(std::vector<pt>, seg&)':
demarcation.cpp:80:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i=0;i<a.size();i++){
      |              ~^~~~~~~~~
demarcation.cpp:84:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int i=1;i<=a.size();i++)sum[i]=sum[i-1]+s[i].get();
      |              ~^~~~~~~~~~
demarcation.cpp:90:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for(int i=1;i<=a.size();i++)if(s[i].type()==2){
      |              ~^~~~~~~~~~
demarcation.cpp:106:30: 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:30: 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:71:2: warning: control reaches end of non-void function [-Wreturn-type]
   71 |  }
      |  ^
demarcation.cpp: In function 'int main()':
demarcation.cpp:131:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  131 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
demarcation.cpp:133:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  133 |  for(pt&p:a)scanf("%lld %lld",&p.x,&p.y);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7768 KB Output is correct
2 Correct 4 ms 6528 KB Output is correct
3 Correct 4 ms 6528 KB Output is correct
4 Incorrect 8 ms 7632 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6528 KB Output is correct
2 Correct 4 ms 6528 KB Output is correct
3 Correct 4 ms 6528 KB Output is correct
4 Correct 4 ms 6528 KB Output is correct
5 Correct 4 ms 6528 KB Output is correct
6 Correct 4 ms 6528 KB Output is correct
7 Correct 4 ms 6528 KB Output is correct
8 Correct 4 ms 6528 KB Output is correct
9 Correct 4 ms 6528 KB Output is correct
10 Incorrect 4 ms 6528 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6528 KB Output is correct
2 Correct 5 ms 6528 KB Output is correct
3 Correct 5 ms 6528 KB Output is correct
4 Correct 4 ms 6528 KB Output is correct
5 Correct 4 ms 6528 KB Output is correct
6 Correct 4 ms 6528 KB Output is correct
7 Correct 4 ms 6528 KB Output is correct
8 Correct 4 ms 6656 KB Output is correct
9 Correct 5 ms 6528 KB Output is correct
10 Correct 4 ms 6528 KB Output is correct
11 Incorrect 4 ms 6528 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7768 KB Output is correct
2 Correct 4 ms 6528 KB Output is correct
3 Correct 4 ms 6528 KB Output is correct
4 Incorrect 8 ms 7632 KB Output isn't correct
5 Halted 0 ms 0 KB -