글 읽기 - 제가 생각하지 못한게 무엇일까요..

bansh123 3년 전 0

일단 코드가 너무 스파게티고 길어 못볼지경이라서 말로 설명드리자면..

벽의 위치를 광원으로부터 가까운 순으로 정렬해서 저장합니다.

가까운벽부터 순서대로 각 벽에 대해서 광원에 의해 만들어지는 그림자의 모양에서 윗부분의 선분(그림자가 시작하는부분)과 아랫부분의 선분을 구합니다.

이때 광원의 위치와 벽에 위치에따라서 그림자의 모양이 상이하기때문에 벽의 위치가 광원 기준으로 1,2,3,4분면, x축 y축중에 어디에 속하는지에 따라 나눠서 생각했고, 그 이외에도 여러가지 있지만 일단 제생각에는 다 고려된것같습니다.)

각 차례마다 만들어진 그림자선분에 포함되는 벽들은 다 제거합니다.

그 후에, 모든 만들어진 선분들을 대상으로, 선분의 시작점, 끝점의 y좌표 , 그리고 선분간 교차점들의 y좌표를 전부 구한 다음에 정렬합니다. (중복값 제거) (혼동될수 있는데 여기서 말하는 y좌표는 0~M값으로 가로축입니다)

그다음 구한 y좌표들에 대해서 아주작은 수 a(ex. 10^(-14))를 더하고 빼서 수직 세로줄 (0,y+a)--(n,y+a), (0,y-a)--(n,y-a) 두 개 만들어서 아까 구했던 모든 그림자 선분들을 대상으로 교차점을 구합니다. (이때 그림자가 시작하는 선분과의 교차점인지 끝나는 선분과의 교차점인지도 마킹해놓습니다.)

다음 마지막으로 이제 각 y좌표들에 대해 그림자인 부분의 길이를 구합니다. 방법은 스위핑기법 활용해서 구했습니다.

그 후에 이를 바탕으로 그림자의 총 넓이를 구했습니다.

제 생각에는 오차범위가 10^(-9)까지 허용되니까 이런 식으로 해도 맞을 것 같아서 짜봤는데 뭘 빠뜨린건지 1%에서 틀렸습니다가 뜨네요..

조언 부탁드립니다!.. 반례라도 주시면 정말 감사하겠습니다!

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
double n, m;
char arr[50][50];
double small = 0.000000000000001;
class A
{
public:
	bool tb;
	double x;
};
class point
{
public:
	double x;
	double y;
};
class sb
{
public:
	point a;
	point b;
};
class boxset
{
public:
	int cond = 0;
	point loc = { 0, 0 };
	vector<sb> top;
	vector<sb> bot;
	vector<sb> T;
};
point source;
vector<point> boxloc;
boxset bs[2500];
vector<double> yidxs;
bool compare(point a, point b)
{
	double dis1 = (a.x - source.x) * (a.x - source.x) + (a.y - source.y) * (a.y - source.y);
	double dis2 = (b.x - source.x) * (b.x - source.x) + (b.y - source.y) * (b.y - source.y);
	return (dis1 < dis2);
}
bool compare2(A a, A b)
{
	return (a.x < b.x);
}
point cal(point a)
{
	point res;
	double X = (double)source.x + 0.5, Y = (double)source.y + 0.5;
	double t, r;
	if (a.x > X)
	{
		t = (n - X) / (double)(a.x - X);
	}
	else {
		t = X / (double)(X - a.x);
	}
	if (a.y > Y)
	{
		r = (m - Y) / (double)(a.y - Y);
	}
	else {
		r = Y / (double)(Y - a.y);
	}
	if (t > r)
	{
		if (a.y > Y)
		{
			res.y = m;
			res.x = X + (double)(a.x - X) * r;
		}
		else
		{
			res.y = 0;
			res.x = X + (double)(a.x - X) * r;
		}
	}
	else
	{
		if (a.x > X)
		{
			res.x = n;
			res.y = Y + (double)(a.y - Y) * t;
		}
		else
		{
			res.x = 0;
			res.y = Y + (double)(a.y - Y) * t;
		}
	}
	return res;
}
bool cross(sb a, sb b, point& cro)
{
	double den = (b.b.y - b.a.y) * (a.b.x - a.a.x) - (b.b.x - b.a.x) * (a.b.y - a.a.y);
	if (den == 0)
	{
		return 0;
	}
	double t = ((b.b.x - b.a.x) * (a.a.y - b.a.y) - (b.b.y - b.a.y) * (a.a.x - b.a.x));
	double s = ((a.b.x - a.a.x) * (a.a.y - b.a.y) - (a.b.y - a.a.y) * (a.a.x - b.a.x));
	if (t == 0 && s == 0)
		return 0;
	t = t / den;
	s = s / den;
	if (t >= 0 && t <= 1 && s >= 0 && s <= 1)
	{
		cro.x = a.a.x + t * (double)(a.b.x - a.a.x);
		cro.y = a.a.y + t * (double)(a.b.y - a.a.y);
		return 1;
	}
	else
	{
		return 0;
	}

}
double sum(int idx)
{
	vector<A>* arr1;
	vector<A>* arr2;
	point temp;
	arr1 = new vector<A>[yidxs.size()];
	arr2 = new vector<A>[yidxs.size()];
	for (int i = 0; i < yidxs.size(); i++)
	{
		if (i == 0)
		{
			for (int j = 0; j <= idx; j++)
			{
				for (int k = 0; k < bs[j].top.size(); k++)
				{
					if (bs[j].top[k].a.x == bs[j].top[k].b.x && bs[j].top[k].a.y == bs[j].top[k].b.y)
						continue;
					if (cross({ { 0,yidxs[i] + small }, { (double)n,yidxs[i] + small} }, bs[j].top[k], temp))
						arr2[i].push_back({ 0,temp.x });
				}
				for (int k = 0; k < bs[j].bot.size(); k++)
				{
					if (bs[j].bot[k].a.x == bs[j].bot[k].b.x && bs[j].bot[k].a.y == bs[j].bot[k].b.y)
						continue;
					if (cross({ { 0,yidxs[i] + small }, { (double)n,yidxs[i] + small } }, bs[j].bot[k], temp))
						arr2[i].push_back({ 1,temp.x });
				}
			}
		}
		else if (i == yidxs.size() - 1)
		{
			for (int j = 0; j <= idx; j++)
			{
				for (int k = 0; k < bs[j].top.size(); k++)
				{
					if (bs[j].top[k].a.x == bs[j].top[k].b.x && bs[j].top[k].a.y == bs[j].top[k].b.y)
						continue;
					if (cross({ { 0,yidxs[i] - small }, { (double)n,yidxs[i] - small } }, bs[j].top[k], temp))
						arr1[i].push_back({ 0,temp.x });
				}
				for (int k = 0; k < bs[j].bot.size(); k++)
				{
					if (bs[j].bot[k].a.x == bs[j].bot[k].b.x && bs[j].bot[k].a.y == bs[j].bot[k].b.y)
						continue;
					if (cross({ { 0,yidxs[i] - small }, { (double)n,yidxs[i] - small } }, bs[j].bot[k], temp))
						arr1[i].push_back({ 1,temp.x });
				}
			}
		}
		else
		{
			for (int j = 0; j <= idx; j++)
			{
				for (int k = 0; k < bs[j].top.size(); k++)
				{
					if (bs[j].top[k].a.x == bs[j].top[k].b.x && bs[j].top[k].a.y == bs[j].top[k].b.y)
						continue;
					if (cross({ { 0,yidxs[i] - small }, { (double)n,yidxs[i] - small } }, bs[j].top[k], temp))
						arr1[i].push_back({ 0,temp.x });
					if (cross({ { 0,yidxs[i] + small }, { (double)n,yidxs[i] + small} }, bs[j].top[k], temp))
						arr2[i].push_back({ 0,temp.x });
				}
				for (int k = 0; k < bs[j].bot.size(); k++)
				{
					if (bs[j].bot[k].a.x == bs[j].bot[k].b.x && bs[j].bot[k].a.y == bs[j].bot[k].b.y)
						continue;
					if (cross({ { 0,yidxs[i] - small }, { (double)n,yidxs[i] - small } }, bs[j].bot[k], temp))
						arr1[i].push_back({ 1,temp.x });
					if (cross({ { 0,yidxs[i] + small }, { (double)n,yidxs[i] + small } }, bs[j].bot[k], temp))
						arr2[i].push_back({ 1,temp.x });
				}
			}
		}
	}
	for (int i = 0; i < yidxs.size(); i++)
	{
		sort(arr1[i].begin(), arr1[i].end(), compare2);
		sort(arr2[i].begin(), arr2[i].end(), compare2);
	}
	double* P1, * P2;
	double X1 = -1;
	int c = 0;
	P1 = new double[yidxs.size()];
	P2 = new double[yidxs.size()];
	for (int i = 0; i < yidxs.size(); i++)
	{
		P1[i] = 0;
		P2[i] = 0;
	}
	for (int i = 0; i < yidxs.size() - 1; i++)
	{
		c = 0;
		X1 = -1;
		for (int j = 0; j < arr2[i].size(); j++)
		{
			if (arr2[i][j].tb == 0)
				c++;
			else
				c--;
			if (c == 1 && X1 == -1)
			{
				X1 = arr2[i][j].x;
			}
			if (c == 0 || j == arr2[i].size() - 1)
			{
				P2[i] += arr2[i][j].x - X1;
				X1 = -1;
			}
		}
	}
	for (int i = 1; i < yidxs.size(); i++)
	{
		c = 0;
		X1 = -1;
		for (int j = 0; j < arr1[i].size(); j++)
		{
			if (arr1[i][j].tb == 0)
				c++;
			else
				c--;
			if (c == 1 && X1 == -1)
			{
				X1 = arr1[i][j].x;
			}
			if (c == 0 || j == arr1[i].size() - 1)
			{
				P1[i] += arr1[i][j].x - X1;
				X1 = -1;
			}
		}
	}
	/*for (int i = 0; i < yidxs.size() - 1; i++)
	{
		cout << P2[i] << " ";
	}
	cout << endl;
	for (int i = 1; i < yidxs.size(); i++)
	{
		cout << P1[i] << " ";
	}
	cout << endl;*/
	double res = 0;
	for (int i = 0; i < yidxs.size() - 1; i++)
	{
		res += (P2[i] + P1[i + 1]) * (yidxs[i + 1] - yidxs[i]) / 2.0;
	}
	return res;
}
void getbs(int idx, int cnt, int sourcecond)
{
	int cond = 0;
	if (boxloc[idx].x == source.x && boxloc[idx].y > source.y)
		cond = 1; // x축, 오른쪽
	else if (boxloc[idx].x < source.x && boxloc[idx].y > source.y)
		cond = 2; // 1사분면
	else if (boxloc[idx].x < source.x && boxloc[idx].y == source.y)
		cond = 3; // y축 위쪽
	else if (boxloc[idx].x < source.x && boxloc[idx].y < source.y)
		cond = 4; // 2사분면
	else if (boxloc[idx].x == source.x && boxloc[idx].y < source.y)
		cond = 5; // x축 왼쪽
	else if (boxloc[idx].x > source.x && boxloc[idx].y < source.y)
		cond = 6; // 3사분면
	else if (boxloc[idx].x > source.x && boxloc[idx].y == source.y)
		cond = 7; // y축 아래
	else
		cond = 8; // 4사분면
	bs[cnt].cond = cond;
	bs[cnt].loc = boxloc[idx];
	point temp1, temp2;
	switch (cond)
	{
	case 1:
		bs[cnt].top.push_back({ boxloc[idx],cal(boxloc[idx]) });
		bs[cnt].bot.push_back({ {boxloc[idx].x + 1,boxloc[idx].y}, cal({boxloc[idx].x + 1,boxloc[idx].y}) });
		if (sourcecond == 3 || sourcecond == 4)
			bs[cnt].top[0] = { boxloc[idx], {0,(double)m} };
		else if (sourcecond == 6 || sourcecond == 7)
			bs[cnt].bot[0] = { {boxloc[idx].x + 1,boxloc[idx].y},{boxloc[idx].x + 1,(double)m} };
		if (cal(boxloc[idx]).x == 0 && sourcecond != 3 && sourcecond != 4 && cal(boxloc[idx]).y != m)
		{
			bs[cnt].top.push_back({ cal(boxloc[idx]),{0,(double)m} });
		}
		if (cal({ boxloc[idx].x + 1,boxloc[idx].y }).x == n && sourcecond != 6 && sourcecond != 7)
		{
			bs[cnt].bot.push_back({ cal({ boxloc[idx].x + 1,boxloc[idx].y }),{(double)n,(double)m} });
		}
		bs[cnt].T.push_back({ boxloc[idx],{boxloc[idx].x + 1,boxloc[idx].y} });
		break;
	case 2:
		bs[cnt].top.push_back({ boxloc[idx],cal(boxloc[idx]) });
		if (boxloc[idx].x == 0)
		{
			bs[cnt].top[0] = { boxloc[idx],{0,cal({boxloc[idx].x + 1,boxloc[idx].y + 1}).y } };
		}
		else if (cal(boxloc[idx]).y != m)
		{
			bs[cnt].top.push_back({ cal(boxloc[idx]),{0,cal({boxloc[idx].x + 1,boxloc[idx].y + 1}).y} });
		}
		bs[cnt].bot.push_back({ {boxloc[idx].x + 1.0,boxloc[idx].y}, { boxloc[idx].x + 1.0,boxloc[idx].y + 1.0 } });
		bs[cnt].bot.push_back({ {boxloc[idx].x + 1.0,boxloc[idx].y + 1.0}, cal({boxloc[idx].x + 1,boxloc[idx].y + 1.0}) });
		bs[cnt].T.push_back({ {boxloc[idx].x + 1.0,boxloc[idx].y},{boxloc[idx].x + 1.0,boxloc[idx].y + 1.0} });
		bs[cnt].T.push_back({ boxloc[idx],{boxloc[idx].x + 1.0,boxloc[idx].y} });
		break;
	case 3:
		bs[cnt].top.push_back({ {0, cal({ boxloc[idx].x + 1,boxloc[idx].y }).y},{0, cal({ boxloc[idx].x + 1,boxloc[idx].y + 1 }).y} });
		bs[cnt].bot.push_back({ cal({ boxloc[idx].x + 1,boxloc[idx].y }),{ boxloc[idx].x + 1,boxloc[idx].y } });
		bs[cnt].bot.push_back({ { boxloc[idx].x + 1,boxloc[idx].y },{ boxloc[idx].x + 1,boxloc[idx].y + 1 } });
		bs[cnt].bot.push_back({ { boxloc[idx].x + 1,boxloc[idx].y + 1 }, cal({ boxloc[idx].x + 1,boxloc[idx].y + 1 }) });
		if (sourcecond == 8 || sourcecond == 1)
		{
			bs[cnt].top[0] = { {0, cal({ boxloc[idx].x + 1,boxloc[idx].y }).y}, {0,(double)m} };
			bs[cnt].bot.pop_back();
		}
		else if (sourcecond == 5 || sourcecond == 6)
		{
			bs[cnt].top[0] = { {0,0}, {0, cal({ boxloc[idx].x + 1,boxloc[idx].y + 1 }).y} };
			bs[cnt].bot.erase(bs[cnt].bot.begin());
		}
		bs[cnt].T.push_back({ {boxloc[idx].x + 1,boxloc[idx].y},{boxloc[idx].x + 1,boxloc[idx].y + 1} });
		break;
	case 4:
		if (cal({ boxloc[idx].x,boxloc[idx].y + 1 }).y != 0)
		{
			bs[cnt].top.push_back({ { 0,cal({boxloc[idx].x + 1,boxloc[idx].y}).y }, cal({boxloc[idx].x,boxloc[idx].y + 1 }) });
		}
		bs[cnt].top.push_back({ cal({boxloc[idx].x,boxloc[idx].y + 1 }),{boxloc[idx].x,boxloc[idx].y + 1 } });
		bs[cnt].bot.push_back({ cal({boxloc[idx].x + 1,boxloc[idx].y}),{boxloc[idx].x + 1,boxloc[idx].y} });
		bs[cnt].bot.push_back({ {boxloc[idx].x + 1,boxloc[idx].y},{boxloc[idx].x + 1,boxloc[idx].y + 1} });
		bs[cnt].T.push_back({ {boxloc[idx].x,boxloc[idx].y + 1},{boxloc[idx].x + 1,boxloc[idx].y + 1} });
		bs[cnt].T.push_back({ {boxloc[idx].x + 1,boxloc[idx].y},{boxloc[idx].x + 1,boxloc[idx].y + 1} });
		break;
	case 5:
		if (cal({ boxloc[idx].x,boxloc[idx].y + 1 }).y != 0)
		{
			bs[cnt].top.push_back({ { 0,0 },{0,cal({ boxloc[idx].x,boxloc[idx].y + 1 }).y } });
		}
		if (cal({ boxloc[idx].x + 1,boxloc[idx].y + 1 }).y != 0)
		{
			bs[cnt].bot.push_back({ { (double)n,0 },{(double)n,cal({ boxloc[idx].x + 1,boxloc[idx].y + 1 }).y } });
		}
		bs[cnt].top.push_back({ cal({boxloc[idx].x,boxloc[idx].y + 1}),{boxloc[idx].x,boxloc[idx].y + 1} });
		bs[cnt].bot.push_back({ cal({boxloc[idx].x + 1,boxloc[idx].y + 1}) ,{boxloc[idx].x + 1,boxloc[idx].y + 1} });
		if (sourcecond == 2 || sourcecond == 3)
		{
			bs[cnt].top[0] = { { 0,0 },{0,boxloc[idx].y + 1} };
			bs[cnt].top.pop_back();
		}
		else if (sourcecond == 7 || sourcecond == 8)
		{
			bs[cnt].bot[0] = { { (double)n,0 },{(double)n,boxloc[idx].y + 1} };
			bs[cnt].bot.pop_back();
		}
		bs[cnt].T.push_back({ {boxloc[idx].x,boxloc[idx].y + 1},{boxloc[idx].x + 1,boxloc[idx].y + 1} });
		break;
	case 6:
		bs[cnt].top.push_back({ cal(boxloc[idx]),boxloc[idx] });
		bs[cnt].top.push_back({ boxloc[idx],{boxloc[idx].x,boxloc[idx].y + 1} });
		if (cal({ boxloc[idx].x + 1,boxloc[idx].y + 1 }).y != 0)
		{
			bs[cnt].bot.push_back({ {n,cal(boxloc[idx]).y}, cal({ boxloc[idx].x + 1,boxloc[idx].y + 1 }) });
		}
		bs[cnt].bot.push_back({ cal({boxloc[idx].x + 1,boxloc[idx].y + 1}),{boxloc[idx].x + 1,boxloc[idx].y + 1} });
		bs[cnt].T.push_back({ {boxloc[idx].x,boxloc[idx].y + 1},{boxloc[idx].x + 1,boxloc[idx].y + 1} });
		bs[cnt].T.push_back({ {boxloc[idx].x,boxloc[idx].y},{boxloc[idx].x,boxloc[idx].y + 1} });
		break;
	case 7:
		bs[cnt].top.push_back({ cal(boxloc[idx]),boxloc[idx] });
		bs[cnt].top.push_back({ boxloc[idx],{boxloc[idx].x,boxloc[idx].y + 1} });
		bs[cnt].top.push_back({ {boxloc[idx].x,boxloc[idx].y + 1},cal({boxloc[idx].x,boxloc[idx].y + 1}) });
		bs[cnt].bot.push_back({ { (double)n,cal(boxloc[idx]).y }, { (double)n,cal({boxloc[idx].x,boxloc[idx].y + 1}).y } });
		if (sourcecond == 2 || sourcecond == 1)
		{
			bs[cnt].bot[0] = { { (double)n,cal(boxloc[idx]).y }, { (double)n,(double)m } };
			bs[cnt].top.pop_back();
		}
		else if (sourcecond == 5 || sourcecond == 4)
		{
			bs[cnt].bot[0] = { { (double)n,0 }, { (double)n,cal({boxloc[idx].x,boxloc[idx].y + 1}).y } };
			bs[cnt].top.erase(bs[cnt].top.begin());
		}
		bs[cnt].T.push_back({ {boxloc[idx].x,boxloc[idx].y},{boxloc[idx].x,boxloc[idx].y + 1} });
		break;
	case 8:
		bs[cnt].top.push_back({ boxloc[idx], {boxloc[idx].x,boxloc[idx].y + 1} });
		bs[cnt].top.push_back({ {boxloc[idx].x,boxloc[idx].y + 1}, cal({boxloc[idx].x,boxloc[idx].y + 1}) });
		bs[cnt].bot.push_back({ {boxloc[idx].x + 1,boxloc[idx].y}, cal({boxloc[idx].x + 1,boxloc[idx].y}) });
		if (cal({ boxloc[idx].x + 1,boxloc[idx].y }).y != m)
		{
			bs[cnt].bot.push_back({ cal({boxloc[idx].x + 1,boxloc[idx].y}),{(double)n,cal({ boxloc[idx].x,boxloc[idx].y + 1 }).y} });
		}
		bs[cnt].T.push_back({ {boxloc[idx].x,boxloc[idx].y},{boxloc[idx].x,boxloc[idx].y + 1} });
		bs[cnt].T.push_back({ boxloc[idx],{boxloc[idx].x + 1,boxloc[idx].y} });
		break;
	}
}
int main()
{
	int numbox = 0, numclbox = 0;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			cin >> arr[i][j];
			if (arr[i][j] == '*')
			{
				source.x = (double)i;
				source.y = (double)j;
			}
			if (arr[i][j] == '#')
			{
				point temp;
				temp.x = (double)i;
				temp.y = (double)j;
				numbox++;
				boxloc.push_back(temp);
			}
		}
	if (numbox == 0)
	{
		cout << 0;
		return 0;
	}
	int sourcecond = 0;
	if (source.x == 0 && source.y == 0)
	{
		sourcecond = 4;
	}
	else if (source.x == 0 && source.y == m - 1.0)
	{
		sourcecond = 2;
	}
	else if (source.x == n - 1.0 && source.y == m - 1.0)
	{
		sourcecond = 8;
	}
	else if (source.x == n - 1.0 && source.y == 0)
	{
		sourcecond = 6;
	}
	else if (source.y == 0)
	{
		sourcecond = 5;
	}
	else if (source.y == m - 1.0)
	{
		sourcecond = 1;
	}
	else if (source.x == 0)
	{
		sourcecond = 3;
	}
	else if (source.x == n - 1.0)
	{
		sourcecond = 7;
	}
	sort(boxloc.begin(), boxloc.end(), compare);
	int idx = 0, cnt = 0;
	double result = 0;
	point temppoint;
	while (1)
	{
		getbs(idx, cnt, sourcecond);
		sb temp;
		temp.a.x = (double)source.x + 0.5;
		temp.a.y = (double)source.y + 0.5;
		for (int i = idx + 1; i < boxloc.size(); i++)
		{
			bool tf1 = 0, tf2 = 0, tf3 = 0, tf4 = 0;
			for (int j = 0; j < bs[cnt].T.size(); j++)
			{
				temp.b.x = (double)boxloc[i].x;
				temp.b.y = (double)boxloc[i].y;
				if (cross(temp, bs[cnt].T[j], temppoint))
					tf1 = 1;
				temp.b.x++;
				if (cross(temp, bs[cnt].T[j], temppoint))
					tf2 = 1;
				temp.b.y++;
				if (cross(temp, bs[cnt].T[j], temppoint))
					tf3 = 1;
				temp.b.x--;
				if (cross(temp, bs[cnt].T[j], temppoint))
					tf4 = 1;
			}
			if (tf1 == 1 && tf2 == 1 && tf3 == 1 && tf4 == 1)
			{
				boxloc.erase(boxloc.begin() + i);
				i--;
				result--;
				numclbox++;
			}
		}
		if (idx + 1 == boxloc.size())
		{
			break;
		}
		idx++;
		cnt++;
	}
	for (int i = 0; i <= idx; i++)
	{
		for (int j = 0; j < bs[i].top.size(); j++)
		{
			yidxs.push_back(bs[i].top[j].a.y);
			yidxs.push_back(bs[i].top[j].b.y);
		}
		for (int j = 0; j < bs[i].bot.size(); j++)
		{
			yidxs.push_back(bs[i].bot[j].a.y);
			yidxs.push_back(bs[i].bot[j].b.y);
		}
	}
	for (int i = 0; i <= idx; i++)
	{
		for (int j = i + 1; j <= idx; j++)
		{
			for (int k = 0; k < bs[i].T.size(); k++)
			{
				for (int l = 0; l < bs[j].bot.size(); l++)
					if (cross(bs[i].T[k], bs[j].bot[l], temppoint))
						yidxs.push_back(temppoint.y);
				for (int l = 0; l < bs[j].top.size(); l++)
					if (cross(bs[i].T[k], bs[j].top[l], temppoint))
						yidxs.push_back(temppoint.y);
				for (int l = 0; l < bs[j].T.size(); l++)
					if (cross(bs[i].T[k], bs[j].T[l], temppoint))
						yidxs.push_back(temppoint.y);
			}
			for (int k = 0; k < bs[i].top.size(); k++)
			{
				for (int l = 0; l < bs[j].bot.size(); l++)
					if (cross(bs[i].top[k], bs[j].bot[l], temppoint))
						yidxs.push_back(temppoint.y);
				for (int l = 0; l < bs[j].top.size(); l++)
					if (cross(bs[i].top[k], bs[j].top[l], temppoint))
						yidxs.push_back(temppoint.y);
				for (int l = 0; l < bs[j].T.size(); l++)
					if (cross(bs[i].top[k], bs[j].T[l], temppoint))
						yidxs.push_back(temppoint.y);
			}
			for (int k = 0; k < bs[i].bot.size(); k++)
			{
				for (int l = 0; l < bs[j].bot.size(); l++)
					if (cross(bs[i].bot[k], bs[j].bot[l], temppoint))
						yidxs.push_back(temppoint.y);
				for (int l = 0; l < bs[j].top.size(); l++)
					if (cross(bs[i].bot[k], bs[j].top[l], temppoint))
						yidxs.push_back(temppoint.y);
				for (int l = 0; l < bs[j].T.size(); l++)
					if (cross(bs[i].bot[k], bs[j].T[l], temppoint))
						yidxs.push_back(temppoint.y);
			}
		}
	}
	sort(yidxs.begin(), yidxs.end());
	auto last = unique(yidxs.begin(), yidxs.end());
	yidxs.erase(last, yidxs.end());
	/*for (int i = 0; i <= idx; i++)
	{
		for (int j = 0; j < bs[i].top.size(); j++)
		{
			cout << bs[i].top[j].a.x << ", " << bs[i].top[j].a.y << "   ";
			cout << bs[i].top[j].b.x << ", " << bs[i].top[j].b.y << endl;
		}

		for (int j = 0; j < bs[i].bot.size(); j++)
		{
			cout << bs[i].bot[j].a.x << ", " << bs[i].bot[j].a.y << "   ";
			cout << bs[i].bot[j].b.x << ", " << bs[i].top[j].b.y << endl;
		}
	}
	cout << endl;
	for (int i = 0; i < yidxs.size(); i++)
	{
		cout << yidxs[i] << " ";
	}
	cout << endl;*/
	result += sum(idx);
	result -= (double)(numbox - numclbox);
	printf("%.15f", result);
}

bansh123 3년 전 4

자답합니다.

일단 small을 너무 작게했던게 문제가 됐었고,

그 다음으론 (0,y)--(n,y)와 선분들의 교차점의 x좌표들이 같은경우에 제가짠 스위핑 기법을 활용하는데 문제가 발생했었습니다.

이 두가지 수정햇더니 드디어 패스했네요!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

제가 생각하지 못한게 무엇일까요..

bansh123 3년 전 0

bansh123 3년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말