Submission #376524

#	Time	Username	Problem	Language	Result	Execution time	Memory
376524		koioi.org-koosaga	색종이 (kriii3_T)	C++17	0 / 109	121 ms	1876 KiB

paper

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using llf = long double;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int MAXN = 205;

template<class T>
struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x=0, T y=0) : x(x), y(y) {}
	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
	P operator+(P p) const { return P(x+p.x, y+p.y); }
	P operator-(P p) const { return P(x-p.x, y-p.y); }
	P operator*(T d) const { return P(x*d, y*d); }
	P operator/(T d) const { return P(x/d, y/d); }
	T dot(P p) const { return x*p.x + y*p.y; }
	T cross(P p) const { return x*p.y - y*p.x; }
	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
	T dist2() const { return x*x + y*y; }
	double dist() const { return sqrt((double)dist2()); }
	// angle to x-axis in interval [-pi, pi]
	double angle() const { return atan2(y, x); }
	P unit() const { return *this/dist(); } // makes dist()=1
	P perp() const { return P(-y, x); } // rotates +90 degrees
	P normal() const { return perp().unit(); }
	// returns point rotated 'a' radians ccw around the origin
	P rotate(double a) const {
		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
};

using punk = Point<llf>;
const llf eps = 1e-14L;
const llf pi = acos(-1);

llf ccw(punk A, punk B, punk C){
	return A.cross(B, C);
}

llf dot(punk A, punk B, punk C){
	return (B - A).dot(C - A);
}

int sgn(llf x){
	if(fabs(x) < eps) return 0;
	return x < 0 ? -1 : 1;
}

struct triangle {
	punk p[3];
	int idx;
	void input(){
		for(int j = 0; j < 3; j++){
			cin >> p[j].x >> p[j].y;
		}
		if(p[0].cross(p[1], p[2]) < 0) swap(p[1], p[2]);
	}
	bool in(punk x){
		for(int j = 0; j < 3; j++){
			if(ccw(p[j], p[(j+1)%3], x) < -eps) return 0;
		}
		return 1;
	}
};

struct circle{
	punk C; llf r;
	int idx;
	bool in(punk x){
		return (C - x).dist2() <= r * r + eps;
	}
	bool operator!=(const circle &c){
		return sgn((c.C - C).dist2()) != 0 || sgn(r - c.r) != 0;
	}
};

template<class P>
int segmentIntersection(const P& s1, const P& e1,
		const P& s2, const P& e2, P& r1, P& r2) {
	if (e1==s1) {
		if (e2==s2) {
			if (e1==e2) { r1 = e1; return 1; } //all equal
			else return 0; //different point segments
		} else return segmentIntersection(s2,e2,s1,e1,r1,r2);//swap
	}
	//segment directions and separation
	P v1 = e1-s1, v2 = e2-s2, d = s2-s1;
	auto a = v1.cross(v2), a1 = v1.cross(d), a2 = v2.cross(d);
	if (a == 0) { //if parallel
		auto b1=s1.dot(v1), c1=e1.dot(v1),
			 b2=s2.dot(v1), c2=e2.dot(v1);
		if (a1 || a2 || max(b1,min(b2,c2))>min(c1,max(b2,c2)))
			return 0;
		r1 = min(b2,c2)<b1 ? s1 : (b2<c2 ? s2 : e2);
		r2 = max(b2,c2)>c1 ? e1 : (b2>c2 ? s2 : e2);
		return 2-(r1==r2);
	}
	if (a < 0) { a = -a; a1 = -a1; a2 = -a2; }
	if (0<a1 || a<-a1 || 0<a2 || a<-a2)
		return 0;
	r1 = s1-v1*a2/a;
	return 1;
}

template<class P>
bool circleIntersection(P a, P b, llf r1, llf r2,
		pair<P, P>* out) {
	P delta = b - a;
	if(delta.dist2() < eps) return false;
	double r = r1 + r2, d2 = delta.dist2();
	double p = (d2 + r1*r1 - r2*r2) / (2.0 * d2);
	double h2 = r1*r1 - p*p*d2;
	if (d2 > r*r || h2 < 0) return false;
	P mid = a + delta*p, per = delta.perp() * sqrt(h2 / d2);
	*out = {mid + per, mid - per};
	return true;
}

bool segmentCircle(punk A, punk B, punk C, llf r, punk &X, punk &Y){
	llf dis = fabs(ccw(A, B, C)) / (B - A).dist();
	if(sgn(dis - r) > 0) return 0;
	punk M = A + (B - A) * (dot(A, B, C) / (B - A).dist2());
	punk D = (B - A).unit() * sqrt(r * r - dis * dis);
	X = M - D;
	Y = M + D;
	return 1;
}

llf dx[MAXN][MAXN];

void solve_circle(circle x, vector<triangle> t, vector<circle> c){
	vector<llf> witness = {0, 2 * pi};
	auto ratio = [&](punk C){
		C = C - x.C;
		assert(fabs(C.dist2() - x.r * x.r) < eps);
		llf ans = atan2l(C.y, C.x);
		while(ans < 0) ans += 2 * pi;
		return ans;
	};
	for(auto &i : t){
		if(x.idx == i.idx) continue;
		for(int j = 0; j < 3; j++){
			punk C = i.p[j];
			punk D = i.p[(j+1)%3];
			punk X, Y;
			if(segmentCircle(C, D, x.C, x.r, X, Y)){
				witness.push_back(ratio(X));
				witness.push_back(ratio(Y));
			}
		}
	}
	for(auto &i : c){
		if(x.idx == i.idx) continue;
		pair<punk, punk> P;
		if(circleIntersection(i.C, x.C, i.r, x.r, &P)){
			witness.push_back(ratio(P.first));
			witness.push_back(ratio(P.second));
		}
	}
	sort(all(witness));
	for(int i = 1; i < sz(witness); i++){
		if(fabs(witness[i] - witness[i - 1]) < eps) continue;
		llf m = (witness[i - 1] + witness[i]) / 2;
		punk M = x.C + punk(x.r, 0).rotate(m);
		int min_idx = -1;
		int max_idx = sz(t) + sz(c);
		for(auto &j : t){
			if(j.idx == x.idx) continue;
			if(j.in(M)){
				if(j.idx < x.idx) min_idx = max(min_idx, j.idx);
				else max_idx = min(max_idx, j.idx);
			}
		}
		for(auto &j : c){
			if(j.idx == x.idx) continue;
			if(j.in(M)){
				if(j.idx < x.idx){
					if(j != x) min_idx = max(min_idx, j.idx);
				}
				else max_idx = min(max_idx, j.idx);
			}
		}
		llf theta = witness[i] - witness[i - 1];
		punk p1 = punk(1, 0).rotate(witness[i - 1]);
		punk p2 = punk(1, 0).rotate(witness[i]);
		llf result = x.r * x.r * theta + x.r * (x.C.cross(p2) - x.C.cross(p1));
	//	printf("%d %d %d %.10Lf\n", min_idx + 1, x.idx, max_idx - 1, result);
		dx[min_idx + 1][x.idx] += result;
		dx[min_idx + 1][max_idx] -= result;
		dx[x.idx + 1][x.idx] -= result;
		dx[x.idx + 1][max_idx] += result;
	}
}

void solve_line(triangle x, vector<triangle> t, vector<circle> c){
	for(int i = 0; i < 3; i++){
		punk A = x.p[i];
		punk B = x.p[(i+1)%3];
		vector<llf> witness = {0, 1};
		auto ratio = [&](punk C){
			if(sgn(A.x - B.x) == 0) return (C.y - A.y) / (B.y - A.y);
			return (C.x - A.x) / (B.x - A.x);
		};
		for(auto &i : t){
			if(x.idx == i.idx) continue;
			for(int j = 0; j < 3; j++){
				punk C = i.p[j];
				punk D = i.p[(j+1)%3];
				if(sgn(ccw(A, B, C)) == 0 && sgn(ccw(A, B, D)) == 0){
					witness.push_back(ratio(C));
					witness.push_back(ratio(D));
				}
				else{
					punk X, Y;
					int val = segmentIntersection(A, B, C, D, X, Y);
					assert(val != 2);
					if(val){
						llf r = ratio(X);
						witness.push_back(r);
					}
				}
			}
		}
		for(auto &i : c){
			punk P, Q;
			if(segmentCircle(A, B, i.C, i.r, P, Q)){
				llf r1 = ratio(P), r2 = ratio(Q);
				if(r1 > r2) swap(r1, r2);
				witness.push_back(r1);
				witness.push_back(r2);
			}
		}
		sort(all(witness));
		for(int i = 1; i < sz(witness); i++){	
		if(fabs(witness[i] - witness[i - 1]) < eps) continue;
			if(witness[i - 1] < -eps || witness[i] > 1 + eps) continue;
			llf m = (witness[i - 1] + witness[i]) / 2;
			auto M = A + (B - A) * m;
			int min_idx = -1;
			int max_idx = sz(t) + sz(c);
			for(auto &j : t){
				if(j.idx == x.idx) continue;
				if(j.in(M)){
					if(j.idx < x.idx) min_idx = max(min_idx, j.idx);
					else max_idx = min(max_idx, j.idx);
				}
			}
			for(auto &j : c){
				if(j.idx == x.idx) continue;
				if(j.in(M)){
					if(j.idx < x.idx) min_idx = max(min_idx, j.idx);
					else max_idx = min(max_idx, j.idx);
				}
			}
			llf result = A.cross(B) * (witness[i] - witness[i - 1]);
			dx[min_idx + 1][x.idx] += result;
			dx[min_idx + 1][max_idx] -= result;
			dx[x.idx + 1][x.idx] -= result;
			dx[x.idx + 1][max_idx] += result;
		}
	}
}

int main(){
	int n; scanf("%d",&n);
	vector<triangle> vt;
	vector<circle> vc;
	for(int i = 0; i < n; i++){
		int t;
		scanf("%d",&t);
		if(t == 1){
			triangle c; c.input();
			vt.push_back(c);
			vt.back().idx = i;
		} else {
			int x, y, r; 
			scanf("%d %d %d",&x,&y,&r);
			vc.push_back({punk(x, y), llf(r)});
			vc.back().idx = i;
		}
	}
	for(auto &i : vt) solve_line(i, vt, vc);
	for(auto &i : vc) solve_circle(i, vt, vc);
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= n; j++){
			if(i) dx[i][j] += dx[i-1][j];
			if(j) dx[i][j] += dx[i][j-1];
			if(i&&j) dx[i][j] -= dx[i-1][j-1];
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= i; j++){
			printf("%.20Lf ", 0.5 * (dx[j][i] - dx[j + 1][i]));
		}
		puts("");
	}
}

Compilation message (stderr)

paper.cpp: In function 'int main()':
paper.cpp:268:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  268 |  int n; scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
paper.cpp:273:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  273 |   scanf("%d",&t);
      |   ~~~~~^~~~~~~~~
paper.cpp:280:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  280 |    scanf("%d %d %d",&x,&y,&r);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~

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