网站建设开票项目是什么,网站开发的公司名称,深圳建站公司价格,企业网站建设公司司正题
题目链接:https://www.luogu.com.cn/problem/CF1019D 题目大意
给出nnn个点#xff0c;保证没有三点共线#xff0c;求是否有三个点围成的三角形面积恰好为SSS。 3≤n≤2103,1≤S≤210183\leq n\leq 2\times 10^3,1\leq S\leq 2\times 10^{18}3≤n≤2103,1≤S≤21018 …正题
题目链接:https://www.luogu.com.cn/problem/CF1019D 题目大意
给出nnn个点保证没有三点共线求是否有三个点围成的三角形面积恰好为SSS。
3≤n≤2×103,1≤S≤2×10183\leq n\leq 2\times 10^3,1\leq S\leq 2\times 10^{18}3≤n≤2×103,1≤S≤2×1018 解题思路
一个暴力的思想是我们可以去枚举底边然后找顶点。
此时底边的长度固定而高度就是顶点离底边所在直线的距离而这题问的是需要找面积为SSS的所以我们可以考虑从近到远二分。
但是如何得到距离直线从近到远的序列因为我们是枚举的我们考虑能否从上次的信息得到这次的信息主要到原来顺序中的一对数x,yx,yx,y满足xxx离的更近当且仅当原来枚举的线段斜率小于xxx到yyy的线段斜率而同理当枚举到斜率大于它时xxx就排到yyy后面了。
那么这样方法就已经很显然了我们把所有点对之间的线段按照斜率从小到大排序枚举然后处理完x→yx\rightarrow yx→y后交换x,yx,yx,y在序列中的顺序就好了这样每次维护好序列后我们就可以二分做了。
时间复杂度O(n2logn2)O(n^2\log n^2)O(n2logn2) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2100;
struct point{ll x,y,id;point(ll xx0,ll yy0){xxx;yyy;}
}a[N],e[N*N/2];
ll n,s,cnt,rk[N],sa[N];
point operator-(point a,point b)
{return point(a.x-b.x,a.y-b.y);}
ll operator^(point a,point b)
{return a.x*b.y-a.y*b.x;}
bool cmp(point x,point y)
{return x.xy.x;}
bool cMp(point x,point y)
{return ((a[x.y]-a[x.x])^(a[y.y]-a[y.x]))0;}
ll calc(point a,point b,point c)
{return abs((b-a)^(c-a));}
signed main()
{freopen(triangle.in,r,stdin);freopen(triangle.out,w,stdout);scanf(%lld%lld,n,s);ss*2ll;for(ll i1;in;i)scanf(%lld%lld,a[i].x,a[i].y);sort(a1,a1n,cmp);for(ll i1;in;i)for(ll j1;ji;j)e[cnt]point(j,i);sort(e1,e1cnt,cMp);for(ll i1;in;i)rk[i]sa[i]i;for(ll i1;icnt;i){ll xe[i].x,ye[i].y;ll l1,rmin(rk[x],rk[y])-1;while(lr){ll mid(lr)1;if(calc(a[x],a[y],a[sa[mid]])s)rmid-1;else lmid1;}if(rcalc(a[x],a[y],a[sa[r]])s){puts(Yes);printf(%lld %lld\n,a[x].x,a[x].y);printf(%lld %lld\n,a[y].x,a[y].y);printf(%lld %lld\n,a[sa[r]].x,a[sa[r]].y);return 0;}swap(rk[x],rk[y]);swap(sa[rk[x]],sa[rk[y]]);}puts(No);return 0;
}
