Submission #38425

#	Time	Username	Problem	Language	Result	Execution time	Memory
38425		kajebiii	레이저 센서 (KOI16_laser)	C++14	100 / 100	409 ms	37072 KiB

laser

#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

int sign(ll x) {return (x>0) - (x<0);}
struct PT{
	int x, y, c, ix;
	PT() {}
	PT(int xx, int yy) : x(xx), y(yy), c(-10), ix(-10) {}
	PT(int xx, int yy, int cc, int ii) : x(xx), y(yy), c(cc), ix(ii) {}
	PT operator-(const PT &o) const{return PT(x-o.x, y-o.y);}
	ll cross(const PT &o) const{return 1ll*x*o.y - 1ll*y*o.x;}
	ll cross(const PT &a, const PT &b) const{return (a-*this).cross(b-*this);}
	int ccw(const PT &o) const{return sign(cross(o));}
	int ccw(const PT &a, const PT &b) const{return sign(cross(a, b));}
};

const int MAX_N = 1e3 + 10;

int N;
vector<PT> Ps;
int Ans[MAX_N][2];

void getAns(vector<PT> &ps) {
	if(SZ(ps) == 0) return;
	int n = SZ(ps);
	for(int i=1; i<n; i++) if(ps[0].y > ps[i].y || ps[0].y == ps[i].y && ps[0].x > ps[i].x) swap(ps[0], ps[i]);
	sort(ps.begin()+1, ps.end(), [&](PT &a, PT &b) {return ps[0].ccw(a, b) > 0;});
	vector<PT> cv; vector<int> index;
	for(int i=0; i<n; i++) {
		while(SZ(cv) >= 2 && cv[SZ(cv)-2].ccw(cv.back(), ps[i]) <= 0) cv.pop_back(), index.pop_back();
		cv.push_back(ps[i]); index.push_back(i);
	}
	int cix = -1;
	for(int i=0; i<SZ(cv); i++) if(cv[i].c == 2) {cix = index[i]; break;}
	{
		vector<PT> t; vector<int> tt;
		swap(t, cv); swap(tt, index);
	}

	if(cix != -1) {
		swap(ps[0], ps[cix]);
		sort(ps.begin()+1, ps.end(), [&](PT &a, PT &b) {return ps[0].ccw(a, b) > 0;});
		int ix = ps[0].ix;
		int now = 2, limit = 1, cnt = 0;
		vector<PT> nps[3];
		for(int i=1; i<n; i++) {
			now += ps[i].c;
			if(ps[i].c == -1 && now == limit && limit != -1) {
				Ans[ix][cnt] = ps[i].ix;
				limit--; cnt++;
			}else nps[cnt].push_back(ps[i]);
		}
		for(int i=0; i<3; i++) getAns(nps[i]);
	}else{
		int now = 0, cnt = 0;
		vector<PT> nps[2]; 
		for(int i=0; i<n; i++) {
			now += ps[i%n].c;
			nps[cnt].push_back(ps[i%n]);
			if(cnt == 0 && now == 0) cnt++;
		}
		if(SZ(nps[1]) == 0) {
			nps[0].clear(); nps[1].clear();
			now = cnt = 0;
			for(int i=n; i>=1; i--) {
				now += ps[i%n].c;
				nps[cnt].push_back(ps[i%n]);
				if(cnt == 0 && now == 0) cnt++;
			}
		}
		for(int i=0; i<2; i++) getAns(nps[i]);
	}
}
int main() {
	cin >> N;
	for(int i=0; i<3*N; i++) {
		int x, y; scanf("%d%d", &x, &y);
		Ps.emplace_back(x, y, i<N?2:-1, i<N?i:i-N);
	}
	getAns(Ps);

	for(int i=0; i<N; i++) printf("%d %d\n", Ans[i][0]+1, Ans[i][1]+1);
	return 0;
}

Compilation message (stderr)

laser.cpp: In function 'void getAns(std::vector<PT>&)':
laser.cpp:36:68: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  for(int i=1; i<n; i++) if(ps[0].y > ps[i].y || ps[0].y == ps[i].y && ps[0].x > ps[i].x) swap(ps[0], ps[i]);
                                                                    ^
laser.cpp: In function 'int main()':
laser.cpp:87:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
                                  ^

• Subtask 1: 14 / 14
• Subtask 2: 19 / 19
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34