新的一周>.<
9.5
cf 340 b
给出 n 个点，求能够形成的四边形的最大面积
最开始的做法是 暴力枚举4个点，再去算面积，不过不对..应该是算面积那里不对
然后应该是枚举四边形的对角线
维护对角线两边的三角形的最大值
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int INF = (1<<30)-1; 8 9 //lrj计算几何模板 10 struct Point 11 { 12 int x, y; 13 Point(double x=0, double y=0) :x(x),y(y) {} 14 }; 15 typedef Point Vector; 16 17 Point read_point(void) 18 { 19 double x, y; 20 scanf("%lf%lf", &x, &y); 21 return Point(x, y); 22 } 23 24 const double EPS = 1e-10; 25 26 //向量+向量=向量 点+向量=点 27 Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); } 28 29 //向量-向量=向量 点-点=向量 30 Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); } 31 32 //向量*数=向量 33 Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); } 34 35 //向量/数=向量 36 Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); } 37 38 bool operator < (const Point& a, const Point& b) 39 { return a.x < b.x || (a.x == b.x && a.y < b.y); } 40 41 int dcmp(double x) 42 { if(fabs(x) < EPS) return 0; else return x < 0 ? -1 : 1; } 43 44 bool operator == (const Point& a, const Point& b) 45 { return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0; } 46 47 /**********************基本运算**********************/ 48 49 //点积 50 double Dot(Vector A, Vector B) 51 { return A.x*B.x + A.y*B.y; } 52 //向量的模 53 double Length(Vector A) { return sqrt(Dot(A, A)); } 54 55 //向量的夹角，返回值为弧度 56 double Angle(Vector A, Vector B) 57 { return acos(Dot(A, B) / Length(A) / Length(B)); } 58 59 //叉积 60 double Cross(Vector A, Vector B) 61 { return A.x*B.y - A.y*B.x; } 62 63 //向量AB叉乘AC的有向面积 64 double Area2(Point A, Point B, Point C) 65 { return Cross(B-A, C-A); } 66 67 //向量A旋转rad弧度 68 Vector VRotate(Vector A, double rad) 69 { 70 return Vector(A.x*cos(rad) - A.y*sin(rad), A.x*sin(rad) + A.y*cos(rad)); 71 } 72 73 //将B点绕A点旋转rad弧度 74 Point PRotate(Point A, Point B, double rad) 75 { 76 return A + VRotate(B-A, rad); 77 } 78 79 //求向量A向左旋转90°的单位法向量,调用前确保A不是零向量 80 Vector Normal(Vector A) 81 { 82 double l = Length(A); 83 return Vector(-A.y/l, A.x/l); 84 } 85 86 /**********************点和直线**********************/ 87 88 //求直线P + tv 和 Q + tw的交点，调用前要确保两条直线有唯一交点 89 Point GetLineIntersection(Point P, Vector v, Point Q, Vector w) 90 { 91 Vector u = P - Q; 92 double t = Cross(w, u) / Cross(v, w); 93 return P + v*t; 94 }//在精度要求极高的情况下，可以自定义分数类 95 96 //P点到直线AB的距离 97 double DistanceToLine(Point P, Point A, Point B) 98 { 99 Vector v1 = B - A, v2 = P - A;100 return fabs(Cross(v1, v2)) / Length(v1); //不加绝对值是有向距离101 }102 103 //点到线段的距离104 double DistanceToSegment(Point P, Point A, Point B)105 {106 if(A == B) return Length(P - A);107 Vector v1 = B - A, v2 = P - A, v3 = P - B;108 if(dcmp(Dot(v1, v2)) < 0) return Length(v2);109 else if(dcmp(Dot(v1, v3)) > 0) return Length(v3);110 else return fabs(Cross(v1, v2)) / Length(v1);111 }112 113 //点在直线上的射影114 Point GetLineProjection(Point P, Point A, Point B)115 {116 Vector v = B - A;117 return A + v * (Dot(v, P - A) / Dot(v, v));118 }119 120 //线段“规范”相交判定121 bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2)122 {123 double c1 = Cross(a2-a1, b1-a1), c2 = Cross(a2-a1, b2-a1);124 double c3 = Cross(b2-b1, a1-b1), c4 = Cross(b2-b1, a2-b1);125 return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;126 }127 128 //判断点是否在线段上129 bool OnSegment(Point P, Point a1, Point a2)130 {131 Vector v1 = a1 - P, v2 = a2 - P;132 return dcmp(Cross(v1, v2)) == 0 && dcmp(Dot(v1, v2)) < 0;133 }134 135 //求多边形面积136 double PolygonArea(Point* P, int n)137 {138 double ans = 0.0;139 for(int i = 1; i < n - 1; ++i){140 double tmp = Cross(P[i]-P[0], P[i+1]-P[0]);141 tmp = fabs(tmp);142 //printf("tmp = %lf\n",tmp);143 ans += tmp;144 }145 return ans/2;146 }147 148 Point p[5],a[505];149 int n;150 151 void solve(){152 double ans = 0.0;153 for(int i = 1;i <= n;i++){154 for(int j = i+1;j <= n;j++){155 double minn = -1.0*INF;156 double maxx = -1.0*INF;157 for(int k = 1;k <= n;k++){158 if(k == i || k == j) continue;159 // printf("i = %d j = %d k = %d ",i,j,k);160 double tmp = Cross(a[i]-a[j], a[k]-a[j]);161 if(tmp < 0) {162 tmp = -tmp;163 minn = max(tmp,minn);164 }165 else maxx = max(maxx,tmp);166 }167 ans = max(ans,(minn+maxx)/2.0);168 }169 }170 printf("%.12lf\n",ans);171 }172 173 int main(){174 while(scanf("%d",&n) != EOF){175 for(int i = 1;i <= n;i++){176 scanf("%d %d",&a[i].x,&a[i].y);177 }178 solve();179 }180 return 0;181 }
9.6
又挂笔试辣
cf 上不去...好不容易码好...心碎..TwT
9.7
cf 429d
定义 f(i,j) = (j-i)^2 + (sum[j]-sum[i])^2
求最小的f(i,j)
没有想出来
先看 f(i,j)像求两点之间距离的样子，所以把点构造成 （i,sum[i]）
就是求平面最近点对了
T 了好几次 是因为抄板抄错了
题目里面现在 的是平方，所以板里面求距离的地方都要平方一下
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 typedef long long LL; 9 const double eps = 1e-8; 10 const LL INF = (1LL << 60);11 const int maxn = 1e5+5;12 int n;13 LL a[maxn];14 15 struct Point{ 16 LL x,y; 17 Point(LL x=0, LL y=0):x(x),y(y) {} 18 bool operator < (const Point& p) const { 19 if(x != p.x) return x < p.x; 20 return y < p.y; 21 } 22 }p[maxn],temp[maxn]; 23 24 bool cmpy(Point a, Point b){ 25 return a.y < b.y; 26 } 27 28 LL Dis(Point a, Point b){ 29 return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); 30 } 31 32 LL sqr(LL x){33 return x*x;34 }35 36 LL Closest_Pair(int left, int right){ 37 LL d = INF; 38 if(left == right) return d; 39 if(left +1 == right) return Dis(p[left],p[right]); 40 int mid = (left+right)>>1; 41 LL d1 = Closest_Pair(left,mid); 42 LL d2 = Closest_Pair(mid+1,right); 43 d = min(d1,d2); 44 int k = 0; 45 for(int i = left; i <= right; i++) { 46 if(sqr(p[mid].x - p[i].x) <= d) 47 temp[k++] = p[i]; 48 } 49 sort(temp,temp+k,cmpy); 50 for(int i = 0; i < k; i++){ 51 for(int j = i+1; j < k && sqr(temp[j].y - temp[i].y) < d; j++){ 52 LL d3 = Dis(temp[i],temp[j]);53 d = min(d,d3);54 } 55 } 56 return d; 57 } 58 59 int main(){ 60 scanf("%d",&n);61 LL sum = 0LL;62 for(int i = 0;i < n;i++){63 scanf("%I64d",&a[i]);64 sum += a[i];65 p[i] = Point(i,sum);66 }67 sort(p,p+n); 68 printf("%I64d\n",Closest_Pair(0,n-1)); 69 return 0;70 }
cf 280 a
给出 一个矩形，再给出它旋转的角度，求这两个矩形相交的面积
第一种 是题目里面那种，解下方程
第二种 是构成两个梯形了，可以拼成一个矩形
wa 成狗
int w,h
double ans = w*h
爆掉了都不知道
还有 就是 感觉打代码好粗心啊，尤其是计算几何就更要细心了
有时候wa 了都不知道咋调
要向司老大学习啊
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 const double PI = acos(-1.0); 9 10 int w,h,a;11 12 void solve(){13 double ans = 0.0;14 if(a > 90) a = 180-a;15 double tot = 1.0*w*h;16 double b = 1.0*a/180.0 * PI;17 if(a == 0 || a == 180){18 ans = 1.0*w*h;19 }20 else if(ans == 90){21 ans = 1.0*w*w;22 }23 else{24 double x,y;25 if(tan(0.5*b) < 1.0*h/w){26 double fz = (h*tan(b)) - (1.0*w)*(1+1.0/(cos(b)));27 double fm = tan(b)*tan(b) - (1.0+1.0/cos(b))*(1.0+1.0/cos(b));28 //printf("fz = %lf fm = %lf\n",fz,fm);29 y = fz/fm;30 fz = h-y*tan(b);31 fm = (1.0+1.0/cos(b));32 x = fz/fm;33 //printf("x = %lf y = %lf\n",x,y);34 double s1 = y*(y*tan(b));35 double s2 = x*(x*tan(b));36 //printf("tot = %lf s1 = %lf s2 = %lf\n",tot,s1,s2);37 ans = tot-s1-s2;38 }39 else{40 ans = tot - (w-1.0*h/sin(b))*h;41 }42 43 }44 printf("%.12lf\n",ans);45 }46 47 int main(){48 while(scanf("%d %d %d",&w,&h,&a) != EOF){49 if(w < h) swap(w,h);50 solve();51 }52 return 0;53 }
9.8
早上写的题不会写dfs_up的
晚上本来有个面试...不知道为什么给调成销售类的了-_-于是就没面了
害得我紧张好一阵
然后开始接着看圆
9.9
cf 600 d
求两个圆相交的面积
相离，内含都是 0
相交的时候，注意到形成了两个全等的三角形，就知道怎么求面积了
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 //lrj计算几何模板 9 struct Point 10 { 11 long double x, y; 12 Point(long double x=0,long double y=0) :x(x),y(y) {} 13 }; 14 typedef Point Vector; 15 16 Point read_point(void) 17 { 18 double x, y; 19 scanf("%lf%lf", &x, &y); 20 return Point(x, y); 21 } 22 23 const double EPS = 1e-10; 24 25 //向量+向量=向量 点+向量=点 26 Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); } 27 28 //向量-向量=向量 点-点=向量 29 Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); } 30 31 //向量*数=向量 32 Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); } 33 34 //向量/数=向量 35 Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); } 36 37 bool operator < (const Point& a, const Point& b) 38 { return a.x < b.x || (a.x == b.x && a.y < b.y); } 39 40 int dcmp(double x) 41 { if(fabs(x) < EPS) return 0; else return x < 0 ? -1 : 1; } 42 43 bool operator == (const Point& a, const Point& b) 44 { return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0; } 45 46 /**********************基本运算**********************/ 47 48 //点积 49 double Dot(Vector A, Vector B) 50 { return A.x*B.x + A.y*B.y; } 51 //向量的模 52 double Length(Vector A) { return sqrt(Dot(A, A)); } 53 54 //向量的夹角，返回值为弧度 55 double Angle(Vector A, Vector B) 56 { return acos(Dot(A, B) / Length(A) / Length(B)); } 57 58 //叉积 59 double Cross(Vector A, Vector B) 60 { return A.x*B.y - A.y*B.x; } 61 62 //向量AB叉乘AC的有向面积 63 double Area2(Point A, Point B, Point C) 64 { return Cross(B-A, C-A); } 65 66 //向量A旋转rad弧度 67 Vector VRotate(Vector A, double rad) 68 { 69 return Vector(A.x*cos(rad) - A.y*sin(rad), A.x*sin(rad) + A.y*cos(rad)); 70 } 71 72 //将B点绕A点旋转rad弧度 73 Point PRotate(Point A, Point B, double rad) 74 { 75 return A + VRotate(B-A, rad); 76 } 77 78 //求向量A向左旋转90°的单位法向量,调用前确保A不是零向量 79 Vector Normal(Vector A) 80 { 81 double l = Length(A); 82 return Vector(-A.y/l, A.x/l); 83 } 84 85 /**********************点和直线**********************/ 86 87 //求直线P + tv 和 Q + tw的交点，调用前要确保两条直线有唯一交点 88 Point GetLineIntersection(Point P, Vector v, Point Q, Vector w) 89 { 90 Vector u = P - Q; 91 double t = Cross(w, u) / Cross(v, w); 92 return P + v*t; 93 }//在精度要求极高的情况下，可以自定义分数类 94 95 //P点到直线AB的距离 96 double DistanceToLine(Point P, Point A, Point B) 97 { 98 Vector v1 = B - A, v2 = P - A; 99 return fabs(Cross(v1, v2)) / Length(v1); //不加绝对值是有向距离100 }101 102 //点到线段的距离103 double DistanceToSegment(Point P, Point A, Point B)104 {105 if(A == B) return Length(P - A);106 Vector v1 = B - A, v2 = P - A, v3 = P - B;107 if(dcmp(Dot(v1, v2)) < 0) return Length(v2);108 else if(dcmp(Dot(v1, v3)) > 0) return Length(v3);109 else return fabs(Cross(v1, v2)) / Length(v1);110 }111 112 //点在直线上的射影113 Point GetLineProjection(Point P, Point A, Point B)114 {115 Vector v = B - A;116 return A + v * (Dot(v, P - A) / Dot(v, v));117 }118 119 //线段“规范”相交判定120 bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2)121 {122 double c1 = Cross(a2-a1, b1-a1), c2 = Cross(a2-a1, b2-a1);123 double c3 = Cross(b2-b1, a1-b1), c4 = Cross(b2-b1, a2-b1);124 return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;125 }126 127 //判断点是否在线段上128 bool OnSegment(Point P, Point a1, Point a2)129 {130 Vector v1 = a1 - P, v2 = a2 - P;131 return dcmp(Cross(v1, v2)) == 0 && dcmp(Dot(v1, v2)) < 0;132 }133 134 //求多边形面积135 double PolygonArea(Point* P, int n)136 {137 double ans = 0.0;138 for(int i = 1; i < n - 1; ++i)139 ans += Cross(P[i]-P[0], P[i+1]-P[0]);140 return ans/2;141 }142 143 /**********************圆的相关计算**********************/144 145 const double PI = acos(-1.0);146 struct Line147 { //有向直线148 Point p;149 Vector v;150 double ang;151 Line() { }152 Line(Point p, Vector v): p(p), v(v) { ang = atan2(v.y, v.x); }153 Point point(double t)154 {155 return p + v*t;156 }157 bool operator < (const Line& L) const158 {159 return ang < L.ang;160 }161 };162 163 struct Circle164 {165 Point c; //圆心166 long double r; //半径167 // Circle(Point c, double r):c(c), r(r) {}168 Point point(double a)169 { //求对应圆心角的点170 return Point(c.x + r*cos(a), c.y + r*sin(a));171 }172 };173 174 175 long double sqr(long double x){ return x*x;}176 177 long double Dis(Point a,Point b){178 long double l = sqr(a.x-b.x);179 long double r = sqr(a.y-b.y);180 return sqrt(sqr(a.x-b.x) + sqr(a.y-b.y));181 }182 183 long double Intersection_area(Circle a,Circle b){ 184 long double dis=Dis(a.c,b.c);185 if(a.r==0||b.r==0||dis>=a.r+b.r)return 0; 186 else if(dis<=fabs(a.r-b.r))return PI*sqr(min(a.r,b.r)); 187 else{ 188 long double angA = 2*acos( (sqr(a.r)+sqr(dis)-sqr(b.r))/(2*a.r*dis) ); 189 long double angB = 2*acos( (sqr(b.r)+sqr(dis)-sqr(a.r))/(2*b.r*dis) ); 190 long double areaA = sqr(a.r)*(angA-sin(angA))/2; 191 long double areaB = sqr(b.r)*(angB-sin(angB))/2; 192 // printf("angA = %llf angB = %llf areaA = %lf areaB = %lf\n",angA,angB,areaA,areaB);193 return areaA+areaB; 194 } 195 } 196 197 Circle a,b;198 199 int main(){200 cin >> a.c.x >> a.c.y >> a.r;201 cin >> b.c.x >> b.c.y >> b.r;202 long double ans = Intersection_area(a,b);203 cout<< setprecision(25) << ans;204 //printf("%.12llf\n",ans);205 return 0;206 }