Submission #1274487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274487		ddddewang	Lonely mdic (kriii1_L)	C++20	0 / 1	3 ms	332 KiB

L

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pll pair<ll,ll>
#define rep(i,a,b) for(register int i=a;i<b;++i)
#define per(i,a,b) for(register int i=a;i>b;--i)
#define F first
#define S second
#define pb push_back
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define mp make_pair
#define full(a) a.begin(),a.end()
#define rfull(a) a.rbegin(),a.rend()

const double pi=acos(-1.0);
const double pii=2*pi;
const double eps=1e-10;

// 기존 유틸리티 함수들 (atan2 사용으로 gth 개선)
inline double sq(double a){ return a*a;}
inline double norm(double th) {
	while (th < 0) th += pii;
	while (th > pii - eps) th -= pii;
	return th;
}
inline bool zero(double a){return abs(a)<eps;}

bool inter(int i,int j,const vector<double>& x,const vector<double>& y,const vector<double>& r){
	double d = sqrt(sq(x[i]-x[j])+sq(y[i]-y[j]));
	if(d > r[i]+r[j] + eps || d < abs(r[i]-r[j]) - eps || d < eps){
		return false;
	}
	return true;
}

void quadratic(double a,double b,double c,double& x1,double& x2){
	double discriminant = sq(b) - 4 * a * c;
	if (discriminant < 0) discriminant = 0;
	x1 = (-b-sqrt(discriminant))/(2*a);
	x2 = (-b+sqrt(discriminant))/(2*a);
}

void lyx(double a,double b,double c,double& x, double& y){
	if(!zero(b)){
		y=(c-a*x)/b;
	}
}

bool lcf(double x,double y,double r,double a,double b, double c,vector<double>& ans){
	double x1,x2,y1,y2;
	if(!zero(b))
	{
		quadratic(1+sq(a/b),-2*x-2*(a/b)*(c/b-y),sq(x)+sq(c/b-y)-sq(r),x1,x2);
		lyx(a,b,c,x1,y1);
		lyx(a,b,c,x2,y2);
		ans = {x1,y1,x2,y2};
	}
	else{
		quadratic(1,-2*y,sq(y)+sq(c/a-x)-sq(r),y1,y2);
		x1=c/a;
		ans={x1,y1,x1,y2};
	}
	return true;
}

inline double gth(double x,double y){
	return norm(atan2(y, x));
}

inline double f1(double x,double y, double r, double theta){
	return 0.5*(r*(x*sin(theta)) - r*(y*cos(theta)) + sq(r)*theta);
}

// ==================================================================
// ## TLE 해결을 위한 새로운 구조
// ==================================================================

// 1. Arc 구조체와 전처리 결과를 저장할 전역 변수
struct Arc {
    double lo, hi;
    int inter_idx;

    bool operator<(const Arc& other) const {
        if (!zero(lo - other.lo)) return lo < other.lo;
        return hi < other.hi;
    }
};

vector<vector<Arc>> precomputed_arcs;

// 2. 전처리 함수: 비싼 계산을 미리 한 번만 수행
void precompute_all_arcs(int n, const vector<double>& x, const vector<double>& y, const vector<double>& r) {
    precomputed_arcs.assign(n, vector<Arc>());
    rep(i, 0, n) {
        rep(j, 0, n) {
            if (i == j) continue;
            if (inter(i, j, x, y, r)) {
                vector<double>交点(4, 0.0);
                lcf(x[i], y[i], r[i], 2 * (x[j] - x[i]), 2 * (y[j] - y[i]), sq(r[i]) - sq(r[j]) + sq(x[j]) - sq(x[i]) + sq(y[j]) - sq(y[i]), 交点);
                double theta1 = gth(交点[0] - x[i], 交点[1] - y[i]);
                double theta2 = gth(交点[2] - x[i], 交点[3] - y[i]);
                
                // 어느 쪽 호가 가려지는지 판별
                if (sq(x[j] - (x[i] + r[i] * cos((theta1 + theta2) / 2.0))) + sq(y[j] - (y[i] + r[i] * sin((theta1 + theta2) / 2.0))) < sq(r[j])) {
                    if (theta1 > theta2) swap(theta1, theta2);
					precomputed_arcs[i].pb({theta1, theta2, j});
                } else {
                    if (theta1 < theta2) swap(theta1, theta2);
                    precomputed_arcs[i].pb({theta1, pii, j});
                    precomputed_arcs[i].pb({0.0, theta2, j});
                }
            }
        }
        sort(full(precomputed_arcs[i]));
    }
}

// 3. f 함수 재정의: 전처리된 정보로 빠르게 넓이 계산
double f(int n, const vector<double>& x, const vector<double>& y, const vector<double>& r) {
    double total_area = 0.0;
    
    vector<bool> is_contained(n, false);
    rep(i, 0, n) {
        if (zero(r[i])) continue; // 반지름 0인 원은 무시
        rep(j, 0, n) {
            if (i == j || zero(r[j])) continue; // 반지름 0인 원은 무시
            double dist = sqrt(sq(x[i] - x[j]) + sq(y[i] - y[j]));
            if (r[j] > r[i] && dist <= r[j] - r[i] + eps) {
                is_contained[i] = true;
                break;
            }
        }
    }

    rep(i, 0, n) {
        if (zero(r[i]) || is_contained[i]) continue;
        
        double current_hi = 0.0;
        for (const auto& arc : precomputed_arcs[i]) {
            // 반지름이 0이거나 포함된 원이 만든 호는 무시
            if (zero(r[arc.inter_idx]) || is_contained[arc.inter_idx]) continue;
            
            if (arc.lo > current_hi) {
                total_area += (f1(x[i], y[i], r[i], arc.lo) - f1(x[i], y[i], r[i], current_hi));
            }
            current_hi = max(current_hi, arc.hi);
        }
        
        // 마지막 남은 구간 [current_hi, 2π]의 넓이 추가
        if (current_hi < pii - eps) {
            total_area += (f1(x[i], y[i], r[i], pii) - f1(x[i], y[i], r[i], current_hi));
        }
    }
    return total_area;
}

// ==================================================================

int main(){
	ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n;cin>>n;
	vector<double> x(n),y(n),r(n);
	for(int i=0;i<n;++i){
		cin>>x[i]>>y[i]>>r[i];
	}

    // ## main 구조는 유지하되, 계산 시작 전 전처리 함수를 한 번 호출
    precompute_all_arcs(n, x, y, r);

	double S = f(n, x, y, r); // 전체 넓이 계산
	int cnt=0;
	for(int i=0;i<n;++i){
        double tmp = r[i];
        if (zero(tmp)) { // 이미 반지름이 0인 경우(중복된 원 등)는 노답원으로 처리 가능
            cnt++;
            continue;
        }
        r[i] = 0; // 임시로 i번째 원 제거
		if(zero(S - f(n, x, y, r))) {
            ++cnt;
        }
        r[i] = tmp; // 원상 복구
	}
	cout<<cnt;
}

Compilation message (stderr)

L.cpp: In function 'void precompute_all_arcs(int, const std::vector<double>&, const std::vector<double>&, const std::vector<double>&)':
L.cpp:96:9: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   96 |     rep(i, 0, n) {
      |         ^
L.cpp:5:37: note: in definition of macro 'rep'
    5 | #define rep(i,a,b) for(register int i=a;i<b;++i)
      |                                     ^
L.cpp:97:13: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   97 |         rep(j, 0, n) {
      |             ^
L.cpp:5:37: note: in definition of macro 'rep'
    5 | #define rep(i,a,b) for(register int i=a;i<b;++i)
      |                                     ^
L.cpp: In function 'double f(int, const std::vector<double>&, const std::vector<double>&, const std::vector<double>&)':
L.cpp:125:9: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  125 |     rep(i, 0, n) {
      |         ^
L.cpp:5:37: note: in definition of macro 'rep'
    5 | #define rep(i,a,b) for(register int i=a;i<b;++i)
      |                                     ^
L.cpp:127:13: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  127 |         rep(j, 0, n) {
      |             ^
L.cpp:5:37: note: in definition of macro 'rep'
    5 | #define rep(i,a,b) for(register int i=a;i<b;++i)
      |                                     ^
L.cpp:137:9: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  137 |     rep(i, 0, n) {
      |         ^
L.cpp:5:37: note: in definition of macro 'rep'
    5 | #define rep(i,a,b) for(register int i=a;i<b;++i)
      |                                     ^

• Subtask 1: 0 / 1