제출 #377299

#제출 시각아이디문제언어결과실행 시간메모리
377299koioi.org-koosaga색종이 (kriii3_T)C++17
36 / 109
239 ms2048 KiB
#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 = 505;
const llf eps = 1e-14L;
const llf pi = acos(-1);

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

llf norm(llf x){
	x = fmod(x, 2 * pi);
	while(x < 0) x += 2 * pi;
	return x;
}


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 sgn(x - p.x) == 0 && sgn(y - p.y) == 0; }
	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); }
	llf 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; }
	llf dist() const { return sqrt((llf)dist2()); }
	// angle to x-axis in interval [-pi, pi]
	llf 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(llf a) const {
		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
};

using punk = Point<llf>;

llf fix(llf x){
	if(sgn(x) == 0) return 0;
	return x;
}

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);
}

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){
		llf dist = (x - C).dist2();
		if(sgn(dist - r * r) > 0) return 0;
		return 1;
	}
	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(sgn(delta.dist2()) == 0) return false;
	llf r = r1 + r2, d2 = delta.dist2();
	llf p = (d2 + (r1 - r2) * (r1 + r2)) / (2.0 * d2);
	llf h2 = r1*r1 - p*p*d2;
	if (d2 > r*r + eps || h2 < -eps) return false;
	P mid = a + delta*p, per = delta.perp() * sqrt(fix(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(fix(r * r - dis * dis));
	X = M - D;
	Y = M + D;
	return 1;
}

llf dx[MAXN][MAXN];
llf ret;

bool sameDirection(punk A, punk B, punk C, punk D){
	return sgn((B - A).dot(D - C)) > 0;
}

/*
   void solve_line(circle x, vector<circle> c){
   punk p[3];
   p[0] = x.T;
   p[1] = x.C;
   p[2] = x.S;
   for(int i = 0; i < 2; i++){
   punk A = p[i];
   punk B = p[i + 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);
   };
   vector<pair<llf, int>> v;
   for(auto &i : c){
   if(x.idx == i.idx) continue;
   vector<llf> witness = {0, 1};
   punk q[3] = {i.T, i.C, i.S};
   for(int j = 0; j < 2; j++){
   punk C = q[j], D = q[j + 1];
   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);
   }
   }
   }
   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));
   auto j = i;
   for(int i = 1; i < sz(witness); i++){	
   if(witness[i - 1] < -eps || witness[i] > 1 + eps) continue;
   llf m = (witness[i - 1] + witness[i]) / 2;
   auto P = A + (B - A) * witness[i - 1];
   auto Q = A + (B - A) * witness[i];
   auto M = A + (B - A) * m;
   bool bad = 0;
   if(j.in(M)){
   bool over = false;
   punk X, Y;
   if(segmentIntersection(P, Q, j.T, j.C, X, Y) == 2 &&
   sameDirection(A, B, j.T, j.C)) over = true;
   if(segmentIntersection(P, Q, j.C, j.S, X, Y) == 2 &&
   sameDirection(A, B, j.C, j.S)) over = true;
   if(over){
   if(j.idx < x.idx) bad = 1;
   }
   else bad = 1;
   }
   if(bad){
   v.emplace_back(witness[i-1], +1);
   v.emplace_back(witness[i], -1);
   }
   }
   }
   v.emplace_back(0, 0);
   v.emplace_back(1, 0);
   sort(all(v));
int bad = 0;
for(int i = 1; i < sz(v); i++){
	bad += v[i-1].second;
	llf result = A.cross(B) * (v[i].first - v[i-1].first);
	if(!bad) ret += result;
}
}
}
*/

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;
		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 - p1);
		for(int i = x.idx; i < max_idx; i++){
			dx[min_idx + 1][i] += result;
			dx[x.idx + 1][i] -= result;
		}
	}
}

	
void solve(){
	int n;
	if(scanf("%d",&n) != 1) exit(0);
	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 <= i; j++){
			printf("%.20Lf ", 0.5 * -dx[j+1][i]);
		}
		puts("");
	}
}

int main(){
	while(1){
		solve();
	}
}

컴파일 시 표준 에러 (stderr) 메시지

paper.cpp: In function 'void solve()':
paper.cpp:304:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  304 |   scanf("%d",&t);
      |   ~~~~~^~~~~~~~~
paper.cpp:311:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  311 |    scanf("%d %d %d",&x,&y,&r);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...