| 记录编号 |
216263 |
评测结果 |
AAAAAAAAAWAWWWWWWWWA |
| 题目名称 |
[国家集训队2011]元素之泉 |
最终得分 |
55 |
| 用户昵称 |
 zhengtn03 |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
0.130 s |
| 提交时间 |
2015-12-28 07:27:01 |
内存使用 |
4.71 MiB |
显示代码纯文本
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<sstream>
#include<iomanip>
#include<stdlib.h>
using namespace std;
#define eps 1.0e-8
#define ll long long
#define INF 2000000000
#define PI acos(-1.0)
int zero(double number)
{
if (abs(number) < eps) return 1;
return 0;
}
struct P3
{
double x, y, z; P3()
{
x = 0; y = 0; z = 0;
}
P3(double x1, double y1, double z1)
{
x = x1;
y = y1;
z = z1;
}
void Scan()
{
scanf("%lf%lf%lf", &x, &y, &z);
}
void Print()const
{
printf("%lf %lf %lf\n", x, y, z);
}
double Length()
{
return sqrt(x*x + y*y + z*z);
}
P3 Unit()
{
double d = sqrt(x*x + y*y + z*z);
if (d > 0)
{
x /= d;
y /= d;
z /= d;
}
return *this;
}
}; P3 p[10010];
int operator ==(const P3 &p1, const P3 &p2)
{
return abs(p1.x - p2.x) <= eps && abs(p1.y - p2.y) <= eps && abs(p1.z - p2.z) <= eps;
}
int operator !=(const P3 &p1, const P3 &p2)
{
return abs(p1.x - p2.x) > eps || abs(p1.y - p2.y) > eps || abs(p1.z - p2.z) > eps;
}
P3 Det(const P3 &p1, const P3 &p2)
{
return P3(p1.y*p2.z - p1.z*p2.y, p1.z*p2.x - p1.x*p2.z, p1.x*p2.y - p1.y*p2.x);
}
double Dot(const P3 &p1, const P3 &p2)
{
return p1.x*p2.x + p1.y*p2.y + p1.z*p2.z;
}
P3 operator +(const P3 &p1, const P3 &p2)
{
return P3(p1.x + p2.x, p1.y + p2.y, p1.z + p2.z);
}
P3 operator -(const P3 &p1, const P3 &p2)
{
return P3(p1.x - p2.x, p1.y - p2.y, p1.z - p2.z);
}
P3 operator *(const P3 &p1, double number)
{
return P3(p1.x * number, p1.y * number, p1.z * number);
}
P3 operator *(double number, const P3 &p1)
{
return P3(p1.x * number, p1.y * number, p1.z * number);
}
P3 operator /(const P3 &p1, double number)
{
return P3(p1.x / number, p1.y / number, p1.z / number);
}
double operator /(const P3 &p1, const P3 &p2)
{
if (!zero(p2.x)) return p1.x / p2.x;
else if (!zero(p2.y)) return p1.y / p2.y;
else if (!zero(p2.z)) return p1.z / p2.z;
return 0;
}
P3 operator -(const P3 &p1)
{
return P3(-p1.x, -p1.y, -p1.z);
}
double Dist(const P3 &p1, const P3 &p2)
{
return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y) + (p1.z - p2.z)*(p1.z - p2.z));
}
void swap(P3 &p1, P3 &p2)
{
P3 temp = p1;
p1 = p2;
p2 = temp;
}
int operator <(const P3 &p1, const P3 &p2)
{
if (p1.x != p2.x) return p1.x < p2.x;
if (p1.y != p2.y) return p1.y < p2.y;
return p1.z < p2.z;
}
struct Line3
{
P3 a, b; Line3()
{
}
Line3(P3 a1, P3 b1)
{
a = a1;
b = b1;
}
void Print()
{
a.Print();
b.Print();
}
}; Line3 l[210];
struct Plane3
{
P3 a, b, c;/*逆时针*/ Plane3()
{
}
Plane3(const P3 &p1, const P3 &p2, const P3 &p3)
{
a = p1;
b = p2;
c = p3;
}
void Print()
{
a.Print();
b.Print();
c.Print();
}
P3 NormalVector()const
{
return Det(a - b, b - c);
}
int On(const P3 &p1)const
{
if (zero(Dot(p1 - a, Det(a - b, b - c)))) return 1;
return 0;
}
}; Plane3 s[210];
struct Ball
{
P3 o; double r; Ball()
{
}
int Inside(const P3 &p)
{
return (Dist(p, o) <= r + eps);
}
}; Ball ball[210];
void DrawPoint(P3 p[], int n)
{
printf("ListPointPlot3D[{");
for (int i = 0; i < n - 1; i++)
{
printf("{%lf,%lf,%lf},", p[i].x, p[i].y, p[i].z);
}
printf("{%lf,%lf,%lf}", p[n - 1].x, p[n - 1].y, p[n - 1].z);
printf("}]");
}
void DrawBall(const Ball &ball)
{
printf("ContourPlot3D[");
printf("(x - %lf)^2 + (y - %lf)^2 + (z - %lf)^2 == %lf", ball.o.x, ball.o.y, ball.o.z, ball.r*ball.r);
printf(", { x, %lf, %lf }", ball.o.x - ball.r, ball.o.x + ball.r);
printf(", { y, %lf, %lf }", ball.o.y - ball.r, ball.o.y + ball.r);
printf(", { z, %lf, %lf }", ball.o.z - ball.r, ball.o.z + ball.r);
printf("]\n");
}
void DrawPlane(const Plane3 &s)
{
printf("ListPlot3D[{");
printf("{%lf, %lf, %lf},", s.a.x, s.a.y, s.a.z);
printf("{%lf, %lf, %lf},", s.b.x, s.b.y, s.b.z);
printf("{%lf, %lf, %lf}", s.c.x, s.c.y, s.c.z);
printf("}]\n");
}
void DrawPlane(Plane3 s[], int n)
{
printf("Show[");
for (int i = 0; i < n; i++)
{
DrawPlane(s[i]);
printf(",");
}
printf("PlotRange -> All]\n");
}
int SamaLine(const P3 &p1, const P3 &p2, const P3 &p3)
{
return zero(Det(p2 - p1, p3 - p1).Length());
}
int SamePlane(const P3 &p1, const P3 &p2, const P3 &p3, const P3 &p4)
{
Plane3 s = Plane3(p1, p2, p3);
return zero(Dot(s.NormalVector(), p4 - p1));
}
int SamePlane(const Line3 &l1, const Line3 &l2)
{
return SamePlane(l1.a, l1.b, l2.a, l2.b);
}
//点在平面法线一侧,不包括平面内
int SameDirection(const P3 &p1, const Plane3 &s1)
{
return Dot(s1.NormalVector(), p1 - s1.a) > eps;
}
int Parallel(const P3 &p1, const P3 &p2)
{
return zero(Det(p1, p2).Length());
}
int Parallel(const Line3 &l1, const Line3 &l2)
{
return zero(Det(l1.b - l1.a, l2.b - l2.a).Length());
}
//和法向量垂直,平行或在平面内
int Parallel(const Line3 &l1, const Plane3 &s1)
{
return zero(Dot(l1.b - l1.a, s1.NormalVector()));
}
int Parallel(const P3 &p1, const Plane3 &s1)
{
return zero(Dot(p1, s1.NormalVector()));
}
int Parallel(const Plane3 &s1, const Plane3 &s2)
{
return Parallel(s1.NormalVector(), s2.NormalVector());
}
int Perpendicular(const P3 &p1, const P3 &p2)
{
return zero(Dot(p1, p2));
}
int Perpendicular(const Line3 &l1, const Line3 &l2)
{
return zero(Dot(l1.b - l1.a, l2.b - l2.a));
}
int Perpendicular(const Plane3 &s1, const Plane3 &s2)
{
//return Parallel(s1.NormalVector(), s2);
return Perpendicular(s1.NormalVector(), s2.NormalVector());
}
//平行算不相交
int Connect(const Line3 &l1, const Line3 &l2, P3 &p)
{
if (SamePlane(l1, l2) == 0) return 0;
if (Parallel(l1, l2)) return 0;
double t = Det(l2.a - l1.a, l2.b - l2.a) / Det(l1.b - l1.a, l2.b - l2.a);
p = (l1.b - l1.a)*t + l1.a;
return 1;
}
P3 Connect(const Line3 &l1, const Line3 &l2)
{
P3 ans;
double t = Det(l2.a - l1.a, l2.b - l2.a) / Det(l1.b - l1.a, l2.b - l2.a);
ans = (l1.b - l1.a)*t + l1.a;
return ans;
}
P3 Connect(const Line3 &l1, const Plane3 &s1)
{
P3 ans;
if (Parallel(l1, s1)) return ans;
P3 ret = s1.NormalVector();
double t = Dot(s1.a - l1.a, ret) / Dot(l1.b - l1.a, ret);
ans = l1.a + t*(l1.b - l1.a);
return ans;
}
int Connect(const Line3 &l1, const Plane3 &s1, P3 &p)
{
if (Parallel(l1, s1)) return 0;
P3 ret = s1.NormalVector();
double t = Dot(s1.a - l1.a, ret) / Dot(l1.b - l1.a, ret);
p = l1.a + t*(l1.b - l1.a);
return 1;
}
int Connect(const Plane3 &s1, const Plane3 &s2, Line3 &l1)
{
if (Parallel(s1, s2)) return 0;
P3 p[3];
Line3 l[3];
l[0] = Line3(s1.a, s1.b);
l[1] = Line3(s1.b, s1.c);
l[2] = Line3(s1.c, s1.a);
int pos = 0;
int flag = -1;
for (int i = 0; i < 3; i++)
{
if (Parallel(l[i], s2) == 0)
{
p[pos] = Connect(l[i], s2);
pos++;
}
else flag = i;
}
if (flag == -1)//三条直线都不平行
{
if (p[0] != p[1]) l1 = Line3(p[0], p[1]);
else l1 = Line3(p[1], p[2]);
}
else l1 = Line3(p[0], p[0] + l[flag].b - l[flag].a);
return 1;
}
double Dist(const P3 &p1, const Line3 &l1)
{
double s1 = abs(Det(p1 - l1.b, p1 - l1.a).Length());
return s1 / Dist(l1.a, l1.b);
}
double Dist(const P3 &p1, const Plane3 &s1)
{
P3 ret = s1.NormalVector();
return Dot(p1 - s1.a, ret) / ret.Length();
}
P3 project(const P3 &p1, const P3 &p2)
{
double d2 = (p2.x*p2.x + p2.y*p2.y + p2.z*p2.z);
if (d2 > 0) return Dot(p1, p2) / d2*p2;
else return P3(0, 0, 0);
}
//异面直线公垂线中点
P3 CommonPerpendicular(const Line3 &l1, const Line3 &l2)
{
P3 p1 = l1.b - l1.a;
P3 p2 = l2.b - l2.a;
P3 ret = Det(p1, p2);
Plane3 s1(l1.a, l1.b, l1.a + ret);
Plane3 s2(l2.a, l2.b, l2.a + ret);
P3 ans1 = Connect(l2, s1);
P3 ans2 = Connect(l1, s2);
return (ans1 + ans2) / 2;
}
P3 FootPoint(const P3 &p1, const Line3 &l1)
{
return l1.a + project(p1 - l1.a, l1.b - l1.a);
}
double area(const P3 &p1, const P3 &p2, const P3 &p3)
{
return abs(Det(p2 - p1, p3 - p1).Length()) / 2;
}
double area(const Plane3 &s1)
{
return abs(Det(s1.b - s1.a, s1.c - s1.a).Length()) / 2;
}
bool cmp1(const P3 &p1, const P3 &p2)
{
if (p1.x != p2.x) return p1.x < p2.x;
if (p1.y != p2.y) return p1.y < p2.y;
return p1.z < p2.z;
}
int InsideTriangle(const P3 &p, const Plane3 &s)//包含边界
{
double s1 = area(s.a, s.b, p);
double s2 = area(s.b, s.c, p);
double s3 = area(s.c, s.a, p);
if (abs(s1 + s2 + s3 - area(s.a, s.b, s.c)) > eps) return 0;
return 1;
}
struct Cube
{
double x1, y1, z1, x2, y2, z2;
Cube()
{
}
Cube(double _x1, double _y1, double _z1, double _x2, double _y2, double _z2)
{
x1 = _x1; y1 = _y1; z1 = _z1; x2 = _x2; y2 = _y2; z2 = _z2;
}
double volume()const
{
return (x2 - x1)*(y2 - y1)*(z2 - z1);
}
int in(const Cube &cube)
{
if (cube.x1 + eps >= x1 && cube.x2 <= x2 + eps &&
cube.y1 + eps >= y1 && cube.y2 <= y2 + eps &&
cube.z1 + eps >= z1 && cube.z2 <= z2 + eps)
return 1;
return 0;
}
void Print()const
{
printf("(%lf,%lf,%lf)(%lf,%lf,%lf)\n", x1, y1, z1, x2, y2, z2);
}
}; Cube cube[210];
struct ConvexHull
{
struct cmp
{
bool operator ()(const P3 &x, const P3 &y)
{
return x < y;
};
};
const static int N = 1001;//点数
struct f
{
int a, b, c;
f(int a1, int b1, int c1)
{
a = a1; b = b1; c = c1;
}
};
vector<f> s;
vector<int> valid;
int vist[N][N];
vector<P3> ConvexHullArea2(P3 p[], int n, const P3 &ret)
{
vector<P3> point1;
if (n == 1){ point1.push_back(p[0]); return point1; }
if (n == 2)
{
if (p[0] == p[1])
{
point1.push_back(p[0]); return point1;
}
else
{
point1.push_back(p[0]);
point1.push_back(p[1]); return point1;
}
}
vector<P3> point2;
sort(p, p + n, cmp1);
point1.push_back(p[0]);
point1.push_back(p[1]);
for (int i = 2; i < n; i++)
{
int pos = point1.size() - 1;
while (1)
{
P3 p2 = p[i] - point1[pos];
P3 p1 = point1[pos] - point1[pos - 1];
if (Dot(Det(p1, p2), ret) > 0)
{
point1.push_back(p[i]);
break;
}
else
{
point1.pop_back();
pos--;
if (pos == 0)
{
point1.push_back(p[i]);
break;
}
}
}
}
point1.pop_back();
point2.push_back(p[n - 1]);
point2.push_back(p[n - 2]);
for (int i = n - 3; i >= 0; i--)
{
int pos = point2.size() - 1;
while (1)
{
P3 p2 = p[i] - point2[pos];
P3 p1 = point2[pos] - point2[pos - 1];
if (Dot(Det(p1, p2), ret) > 0)
{
point2.push_back(p[i]);
break;
}
else
{
point2.pop_back();
pos--;
if (pos == 0)
{
point2.push_back(p[i]);
break;
}
}
}
}
point1.insert(point1.end(), point2.begin(), point2.end());//起点和终点是同一点
point1.pop_back();
return point1;
}
void DFS(P3 p[], int i, int j)
{
int number = vist[s[j].b][s[j].a];
if (valid[number])
{
Plane3 tempS = Plane3(p[s[number].a], p[s[number].b], p[s[number].c]);
if (SameDirection(p[i], tempS))
{
valid[number] = 0;
DFS(p, i, number);
}
else
{
Plane3 tempS = Plane3(p[s[j].a], p[s[j].b], p[i]);
f tempF = f(s[j].a, s[j].b, i);
for (int k = 0; k < i; k++)
{
if (tempS.On(p[k]) == 0)//找到不在平面内一点
{
if (SameDirection(p[k], tempS)) swap(tempF.a, tempF.b);//使法线朝外
break;
}
}
s.push_back(tempF);
valid.push_back(1);
vist[tempF.a][tempF.b] = s.size() - 1;
vist[tempF.b][tempF.c] = s.size() - 1;
vist[tempF.c][tempF.a] = s.size() - 1;
}
}
number = vist[s[j].c][s[j].b];
if (valid[number])
{
Plane3 tempS = Plane3(p[s[number].a], p[s[number].b], p[s[number].c]);
if (SameDirection(p[i], tempS))
{
valid[number] = 0;
DFS(p, i, number);
}
else
{
Plane3 tempS = Plane3(p[s[j].b], p[s[j].c], p[i]);
f tempF = f(s[j].b, s[j].c, i);
for (int k = 0; k < i; k++)
{
if (tempS.On(p[k]) == 0)//找到不在平面内一点
{
if (SameDirection(p[k], tempS)) swap(tempF.a, tempF.b);//使法线朝外
break;
}
}
s.push_back(tempF);
valid.push_back(1);
vist[tempF.a][tempF.b] = s.size() - 1;
vist[tempF.b][tempF.c] = s.size() - 1;
vist[tempF.c][tempF.a] = s.size() - 1;
}
}
number = vist[s[j].a][s[j].c];
if (valid[number])
{
Plane3 tempS = Plane3(p[s[number].a], p[s[number].b], p[s[number].c]);
if (SameDirection(p[i], tempS))
{
valid[number] = 0;
DFS(p, i, number);
}
else
{
Plane3 tempS = Plane3(p[s[j].a], p[s[j].c], p[i]);
f tempF = f(s[j].a, s[j].c, i);
for (int k = 0; k < i; k++)
{
if (tempS.On(p[k]) == 0)//找到不在平面内一点
{
if (SameDirection(p[k], tempS)) swap(tempF.a, tempF.b);//使法线朝外
break;
}
}
s.push_back(tempF);
valid.push_back(1);
vist[tempF.a][tempF.b] = s.size() - 1;
vist[tempF.b][tempF.c] = s.size() - 1;
vist[tempF.c][tempF.a] = s.size() - 1;
}
}
}
vector<P3> ConvexHullArea3(P3 p[], int n)
{
vector<P3> ans;
int pos = 1;
for (int i = 1; i < n; i++)
{
if (p[0] != p[i]) swap(p[1], p[i]); pos = 2; break;
}
if (pos != 2){ ans.push_back(p[0]); return ans; }//共点
for (int i = 2; i < n; i++)
{
if (SamaLine(p[0], p[1], p[i]) == 0) swap(p[2], p[i]); pos = 3; break;
}
if (pos != 3)
{
sort(p, p + n, cmp1);
ans.push_back(p[0]);
ans.push_back(p[n - 1]);
return ans;//所有点共线
}
for (int i = 3; i < n; i++)
{
if (SamePlane(p[0], p[1], p[2], p[i]) == 0) swap(p[3], p[i]); pos = 4; break;
}
if (pos != 4)
{
P3 ret;//规定一个平面的方向
ret = Plane3(p[0], p[1], p[2]).NormalVector();
if (zero(ret.z) != 0)
{
if (ret.z < 0) ret = -ret;
}
else if (zero(ret.y) != 0)
{
if (ret.y > 0) ret = -ret;
}
else if (zero(ret.x) != 0)
{
if (ret.x < 0) ret = -ret;
}
ret.Unit();
return ConvexHullArea2(p, n, ret);//调用二维凸包
}
for (int i = 0; i < 4; i++)
{
Plane3 tempS = Plane3(p[(i + 1) % 4], p[(i + 2) % 4], p[(i + 3) % 4]);
f tempF = f((i + 1) % 4, (i + 2) % 4, (i + 3) % 4);
if (SameDirection(p[i], tempS)) swap(tempF.a, tempF.b);//使法线朝外
s.push_back(tempF);
valid.push_back(1);
vist[tempF.a][tempF.b] = i;
vist[tempF.b][tempF.c] = i;
vist[tempF.c][tempF.a] = i;
}
for (int i = 4; i < n; i++)
{
for (int j = 0; j < s.size(); j++)
{
if (valid[j] == 1)//面在外面
{
Plane3 tempS = Plane3(p[s[j].a], p[s[j].b], p[s[j].c]);
if (SameDirection(p[i], tempS))
{
valid[j] = 0;
DFS(p, i, j);
break;
}
}
}
}
set<int> outPoint;
set<int>::iterator ite;
for (int i = 0; i < s.size(); i++)
{
if (valid[i] == 1)
{
outPoint.insert(s[i].a);
outPoint.insert(s[i].b);
outPoint.insert(s[i].c);
}
}
for (ite = outPoint.begin(); ite != outPoint.end(); ite++)
{
ans.push_back(p[*ite]);
}
return ans;
}
}; ConvexHull hull;
double a[10010];
P3 p1[10010];
struct cmp
{
bool operator ()(const P3 &x, const P3 &y)
{
return x < y;
};
};
int main()
{
freopen("nt2011_spring.in", "r", stdin);
freopen("nt2011_spring.out", "w", stdout);
int n, m;
scanf("%d%d", &n, &m);
int ans = 0;
if (m == 1)
{
for (int i = 0; i < n; i++)
{
double temp;
scanf("%lf", &temp);
}
if (n == 1) ans = 0;
else ans = n;
}
else if (m == 2)
{
for (int i = 0; i < n; i++)
{
scanf("%lf", a + i);
double temp;
scanf("%lf", &temp);
}
sort(a, a + n);
if (n == 1) ans = 0;
ans = n - 2;
if (abs(a[0] - a[1]) < eps) ans++;
if (abs(a[n - 1] - a[n - 2]) < eps) ans++;
}
else if (m == 3)
{
map<P3, int, cmp> m;
for (int i = 0; i < n; i++)
{
p[i].Scan();
p[i].z = 0;
m[p[i]]++;
}
sort(p, p + n, cmp1);
int count1 = 0;
p1[count1] = p[0];
count1++;
for (int i = 1; i < n; i++)
{
if (p[i] != p[i - 1])
{
p1[count1] = p[i];
count1++;
}
}
vector<P3> temp = hull.ConvexHullArea2(p1, count1, P3(0, 0, 1));
ans = n - temp.size();
for (int i = 0; i < temp.size(); i++)
{
if (m[temp[i]] != 1) ans++;
}
}
else if (m == 4)
{
map<P3, int, cmp> m;
for (int i = 0; i < n; i++)
{
double temp;
scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].z);
m[p[i]]++;
}
sort(p, p + n, cmp1);
int count1 = 0;
p1[count1] = p[0];
count1++;
for (int i = 1; i < n; i++)
{
if (p[i] != p[i - 1])
{
p1[count1] = p[i];
count1++;
}
}
vector<P3> temp = hull.ConvexHullArea3(p1, count1);
ans = n - temp.size();
for (int i = 0; i < temp.size(); i++)
{
if (m[temp[i]] != 1) ans++;
}
}
printf("%d\n", ans);
return 0;
}