| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 15471 |
2015-07-12T08:12:55 Z |
myungwoo |
색종이 (kriii3_T) |
C++14 |
|
1000 ms |
2688 KB |
#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1000 ms |
2688 KB |
Program timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
