Submission #15474

#	Time	Username	Problem	Language	Result	Execution time	Memory
15474		myungwoo	색종이 (kriii3_T)	C++14	0 / 109	1000 ms	2688 KiB

paper

#pragma warning(disable:4996)

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

struct point {
	double x, y, z;
	point(){}
	point(double x, double y, double z=1) : x(x), y(y), z(z) {}
	
	double dot(const point& r) const { return x*r.x + y*r.y; }
	double size() const { return sqrt(x*x + y*y); }
	double angle() const { return atan2(y, x); }

	point proj() const { return point(x/z, y/z); }

	point operator - (const point& r) const { return point(x-r.x, y-r.y); }
	point operator + (const point& r) const { return point(x+r.x, y+r.y); }
	
	point operator * (const double& r) const { return point(x*r, y*r); }

	point operator * (const point& r) const { return point(y*r.z - z*r.y, z*r.x - x*r.z, x*r.y - y*r.x); }
};

int n;
point v[200][3];
double r[200];

double sum[200][200];

vector<double> x;

void int_cc(point p1, double r1, point p2, double r2)
{
	if (r1 > r2) {
		int_cc(p2, r2, p1, r1);
		return;
	}

	double d = (p2-p1).size();
	if (r1+r2 < d || r2 - r1 > d) return;

	double t = (p2-p1).angle();
	double dt = acos( (r1*r1 + d*d - r2*r2) / (2*r1*d) );

	point i1 = p1 + point(r1 * cos(t+dt), r1 * sin(t+dt));
	point i2 = p1 + point(r1 * cos(t-dt), r1 * sin(t-dt));

	x.push_back(i1.x);
	x.push_back(i2.x);
}

void int_cl(point p1, double r1, point p21, point p22)
{
	// l: (1-t)p21 + tp22 = t(p22-p21) + p21
	// (p1 - p21 - t(p22-p21))^2 = r1^2
	// t^2 (p22-p21)^2 - 2t(p22-p21)(p1-p21) + (p1-p21)^2 - r1^2 = 0

	double a = (p22-p21).dot(p22-p21);
	double b = -(p22-p21).dot(p1-p21);
	double c = (p1-p21).dot(p1-p21) - r1*r1;
	double D = b*b - a*c;
	if (D<0) return;

	double t1 = (-b + sqrt(D)) / a;
	double t2 = (-b - sqrt(D)) / a;

	point i1 = p21 + (p22 - p21) * t1;
	point i2 = p21 + (p22 - p21) * t2;

	if (0<=t1 && t1<=1) x.push_back(i1.x);
	if (0<=t2 && t2<=1) x.push_back(i2.x);
}

void int_ct(point p1, double r1, point p2[])
{
	for (int i=0; i<3; i++)
		int_cl(p1, r1, p2[i], p2[(i+1)%3]);
}

bool inBox(point x, point b1, point b2)
{
	return
		min(b1.x, b2.x) <= x.x && x.x <= max(b1.x, b2.x) &&
		min(b1.y, b2.y) <= x.y && x.y <= max(b1.y, b2.y) ;
}

void int_ll(point p11, point p12, point p21, point p22)
{
	point l1(p11 * p12);
	point l2(p11 * p12);
	point i = l1 * l2;

	if (fabs(i.z) > 1e-4) {
		i = i.proj();
		if (inBox(i, p11, p12) && inBox(i, p21, p22))
			x.push_back(i.x);
	}
}

void int_tt(point p1[], point p2[])
{
	for (int i=0; i<3; i++) for (int j=0; j<3; j++)
		int_ll(p1[i], p1[(i+1)%3], p2[j], p2[(j+1)%3]);
}

double eval_c(point p, double r, int dir, double x)
{
	// (px - x)^2 + (py - y)^2 = r^2
	// py - y = +- sqrt(r^2 - dx^2)
	// y = py +- sqrt(r^2 - dx^2)

	double dx = x - p.x;
	double D = r*r - dx*dx;
	if (D<0) D = 0;
	return dir == 1 ? p.y + sqrt(D) : p.y - sqrt(D);
}

double eval_t(point p[], int dir, double x)
{
	bool f = false;
	double y = 0.;

	for (int i=0; i<3; i++) {
		point p1 = p[i];
		point p2 = p[(i+1)%3];

		if (min(p1.x, p2.x) <= x && x <= max(p1.x, p2.x)) {
			double ny = p1.y + (p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x);
			if (!f) {
				f = true;
				y = ny;
			}
			if (dir == 1  && y < ny) y = ny;
			if (dir == -1 && y > ny) y = ny;
		}
	}

	return y;
}

double area_c(point p, double r, int dir, double x1, double x2)
{
	double t1 = acos((x1-p.x) / r);
	double t2 = acos((x2-p.x) / r);
	double i = r*r/4 * (sin(2*t2) - sin(2*t1)) - r*r/2 * (t2-t1);

	return (x2-x1) * p.y + dir * i;
}

double area_t(point p[], int dir, double x1, double x2)
{
	bool f = false;
	double y = 0.;
	int id = -1;

	double x = (x1+x2)/2;

	for (int i=0; i<3; i++) {
		point p1 = p[i];
		point p2 = p[(i+1)%3];

		if (min(p1.x, p2.x) <= x && x <= max(p1.x, p2.x)) {
			double ny = p1.y + (p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x);
			if (!f) {
				f = true;
				y = ny, id = i;
			}
			if (dir == 1  && y < ny) y = ny, id = i;
			if (dir == -1 && y > ny) y = ny, id = i;
		}
	}
	
	point p1 = p[id];
	point p2 = p[(id+1)%3];
	double y1 = p1.y + (p2.y - p1.y) / (p2.x - p1.x) * (x1 - p1.x);
	double y2 = p1.y + (p2.y - p1.y) / (p2.x - p1.x) * (x2 - p1.x);

	return (y1+y2)/2 * (x2-x1);
}

struct segment {
	int i, dir;
	double x, y;

	segment(int i, int dir, double x) : i(i), dir(dir), x(x)
	{
		if (r[i]) y = eval_c(v[i][0], r[i], dir, x);
		else y = eval_t(v[i], dir, x);
	}

	bool operator < (const segment& rhs) const { return y < rhs.y; }
};

void solve(double x1, double x2)
{
	double x = (x1+x2)/2;
	vector<segment> s;

	for (int i=0; i<n; i++) {
		if (r[i]) {
			if (v[i][0].x - r[i] <= x && x <= v[i][0].x + r[i]) {
				s.push_back(segment(i, -1, x));
				s.push_back(segment(i, +1, x));
			}
		}
		else {
			if (min(v[i][0].x, min(v[i][1].x, v[i][2].x)) <= x && x <= max(v[i][0].x, max(v[i][1].x, v[i][2].x))) {
				s.push_back(segment(i, -1, x));
				s.push_back(segment(i, +1, x));
			}
		}
	}

	sort(s.begin(), s.end());

	set<int> l;

	for (int i=0; i<s.size()-1; i++) {
		double a;

		if (r[ s[i+1].i ]) a = area_c(v[s[i+1].i][0], r[s[i+1].i], s[i+1].dir, x1, x2);
		else a = area_t(v[s[i+1].i], s[i+1].dir, x1, x2);

		if (r[ s[i].i ]) a -= area_c(v[s[i].i][0], r[s[i].i], s[i].dir, x1, x2);
		else a -= area_t(v[s[i].i], s[i].dir, x1, x2);

		if (s[i].dir == -1) l.insert(s[i].i);
		else l.erase(s[i].i);

		/*
		int prev = -1;
		for (int v : l) {
			if (prev != -1)
				sum[v][prev] -= a;
			sum[v][v] += a;
			prev = v;
		}*/
	}
}

int main()
{
	scanf("%d", &n);
	for (int i=0; i<n; i++) {
		int t;
		scanf("%d", &t);
		if (t==1) {
			double x1, y1, x2, y2, x3, y3;
			scanf("%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3);
			v[i][0] = point(x1, y1);
			v[i][1] = point(x2, y2);
			v[i][2] = point(x3, y3);
		}
		else {
			double x, y, rr;
			scanf("%lf%lf%lf", &x, &y, &rr);
			v[i][0] = point(x, y);
			r[i] = rr;
		}
	}

	for (int i=0; i<n; i++) {
		if (r[i]) {
			x.push_back(v[i][0].x - r[i]);
			x.push_back(v[i][0].x + r[i]);
		}
		else {
			for (int j=0; j<3; j++)
				x.push_back(v[i][j].x);
		}
	}

	for (int i=0; i<n; i++) for (int j=i+1; j<n; j++) {
		if (r[i] && r[j]) int_cc(v[i][0], r[i], v[j][0], r[j]);
		else if (r[i]) int_ct(v[i][0], r[i], v[j]);
		else if (r[j]) int_ct(v[j][0], r[j], v[i]);
		else int_tt(v[i], v[j]);
	}

	sort(x.begin(), x.end());
	x.resize( unique(x.begin(), x.end()) - x.begin() );

	for (int i=0; i<x.size()-1; i++)
		solve(x[i], x[i+1]);

	for (int i=0; i<n; i++) for (int j=i+1; j<n; j++)
		sum[j][i] += sum[j-1][i];

	for (int i=0; i<n; i++) {
		for (int j=0; j<=i; j++)
			printf("%.15lf ", sum[i][j]);
		printf("\n");
	}

	return 0;
}

• Subtask 1: 0 / 36
• Subtask 2: 0 / 73