| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1274493 | ddddewang | Lonely mdic (kriii1_L) | C++20 | 0 ms | 0 KiB |
#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> ans(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(ans[0] - x[i], ans[1] - y[i]);
double theta2 = gth(ans[2] - x[i], ans[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;
rep(j, 0, n) {
if (i == j || zero(r[j])) continue;
double dist = sqrt(sq(x[i] - x[j]) + sq(y[i] - y[j]));
// ## 수정된 포함 조건 ##
// 1. 일반적인 포함 관계 (j가 i를 포함)
bool strict_contain = (r[j] > r[i] && dist <= r[j] - r[i] + eps);
// 2. 완전히 겹치는 원일 경우, 인덱스가 큰 쪽이 작은 쪽을 포함하도록 규칙 적용
bool identical_contain = (zero(r[j] - r[i]) && zero(dist) && j > i);
if (strict_contain || identical_contain) {
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;
}