首页 > 其他分享 >CSU 1812 三角形和矩形

CSU 1812 三角形和矩形

时间:2022-11-09 19:34:54浏览次数:40  
标签:矩形 1812 get int double mid CSU include define


Description


Bobo 有一个三角形和一个矩形,他想求他们交的面积。



1,y 1,x 2,y 2,x 3,y 3,x 4,y 4 描述。 表示三角形的顶点坐标是 (x 1,y 1),(x 1,y 2),(x 2,y 1), 矩形的顶点坐标是 (x 3,y 3),(x 3,y 4),(x 4,y 4),(x 4,y 3).


Input


输入包含不超过 30000 组数据。



1,y 1,x 2,y 2 (x 1≠x 2,y 1≠y 2).



3,y 3,x 4,y 4 (x 3<x 4,y 3<y 4).



i,y i≤10 4)


Output


-6


Sample Input

1 1 3 3
0 0 2 2
0 3 3 1
0 0 2 2
4462 1420 2060 2969
4159 257 8787 2970

Sample Output

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define ff first
#define ss second
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define pii pair<int,LL>
#define in(x) scanf("%d", &x);
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-9;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int T, n, m;
int x[5], y[5];

double get(double g)
{
if (g < min(x[1], x[2]) || g > max(x[1], x[2])) return -INF;
double k = 1.0*fabs(g - x[2]) / fabs(x[1] - x[2]);
double L = y[1], R = y[1] + (y[1] < y[2] ? k : -k)*abs(y[1] - y[2]);
if (L > R) swap(L, R);
return max(min(1.0*y[4], R) - max(1.0*y[3], L), 0.0);
}

int main()
{
while (scanf("%d%d", &x[1], &y[1]) != EOF)
{
rep(i, 2, 4) scanf("%d%d", &x[i], &y[i]);
double L = get(x[3]), ans = 0;
rep(i, x[3] + 1, x[4])
{
double R = get(i);
if (L != -INF && R != -INF)
{
if (fabs(L + R - 2 * get(i - 0.5)) < eps) ans += (L + R) / 2;
else
{
double l = i - 1, r = i;
while (l + eps < r)
{
double mid = (l + r) / 2;
if (fabs(get(mid) - L) < eps) l = mid; else r = mid;
}
double q = i - 1, h = i;
while (q + eps < h)
{
double mid = (q + h) / 2;
if (fabs(get(mid) - R) < eps) h = mid; else q = mid;
}
ans += L*(l - i + 1) + R*(i - q) + (L + R)*(q - l) / 2;
}
}
L = R;
}
printf("%.8lf\n", ans);
}
return 0;
}

标签:矩形,1812,get,int,double,mid,CSU,include,define
From: https://blog.51cto.com/u_15870896/5838617

相关文章

  • CSU 1808 地铁
    Description Bobo居住在大城市ICPCCamp。i 号线,位于站ai,bi 之间,往返均需要花费ti 分钟(即从ai 到bi 需要ti 分钟,从bi 到ai......
  • CSU 1810 Reverse
    Description1 d2…dn1…di-1 dj dj-1…di dj+1 dj+2…dn.Bobowouldliketofind9+7).InputTheinputcontains......
  • CSU 1809 Parenthesis
    Description1 p2…pnai andpbiParenthesissequenceSisbalancedifandonlyif:Sisempty;orthereexists balanced parenthesi......
  • CSU 1804 有向无环图
    DescriptionBobo有一个n个点,m条边的有向无环图(即对于任意点v,不存在从点v开始、点v结束的路径)。为了方便,点用1,2,…,n编号。设count(x,y)表示点x......
  • CSU 1803 2016
    Description 给出正整数n和m,统计满足以下条件的正整数对(a,b)的数量:1.1≤a≤n,1≤b≤m;2.a×b是2016的倍数。Input......
  • 611005 CAD 多边形矩形圆弧圆
    本节课讲解5CAD多边形矩形圆弧圆。1.多边形快捷键【POL】,输入侧面数,可以选择【内切】或【外接】。2.内切的图形在圆形内,外接的图形在圆形外面,参数一样的情况下,图形大......
  • 【Java[类的创建与使用]】7-5 设计一个矩形类Rectangle
    编写一个Java应用程序,该程序包含两个类,类的定义如下:(1)一个有关计算矩形面积的类Rectangle,定义如下成员:①两个私有的成员变量:length(长,double类型)、width(宽,double类型);......
  • BZOJ 1185([HNOI2007]最小矩形覆盖-旋转卡壳+点集几何意义)
    1185:[HNOI2007]最小矩形覆盖TimeLimit: 10Sec  MemoryLimit: 162MBSec  SpecialJudgeSubmit: 258  Solved: 137Description l要事先改成......
  • RQNOJ 698(矩形计数-圆内接矩形数)
    查看题目ShowProblem题目:矩形计数问题编号:698题目描述给出圆周上的N个点,请你计算出以这些点中的任意四个为四个角,能构成多少个矩形。点的坐标是这样描述的,给定一......
  • csu 1554: SG Value 思维题
    ​​http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1554​​这题在比赛的时候居然没想出来,然后发现居然是做过的题目的变种!!!!先不考虑插入操作,就给定一堆数字,求出不能......