当前位置: 代码迷 >> 综合 >> cf 1163C2. Power Transmission (Hard Edition)(几何,给定1e3个点求两条线相交的组数)
  详细解决方案

cf 1163C2. Power Transmission (Hard Edition)(几何,给定1e3个点求两条线相交的组数)

热度:10   发布时间:2024-03-10 00:53:51.0

题目链接:https://codeforces.ml/contest/1163/problem/C2

题意:

n表示给定点的个数,xi,yi为坐标。

在一条线上的点只需要用一条线相连。

题解:

1.k用pair<int,int>存储最简分式(就不用考虑精度问题了)。

2.map<pii,ll> mp;将斜率映射成id(下标)。

3.存储每条线,只需要k和d。st1[mp[{kx,ky}].insert({dx,dy});//表示一条线。

4.该题求解:先预处理(第一次做,想了一下午,从毫无思路到一发AC,还是很值得的)。st1[mp[k]].insert(b).

所有st1[i].size()的值为sum(即总边数)。

ans+=(sum-st1[mp[k]].pb(b))*st1[mp[k]].pb(b);//表示斜率非k的边数*斜率为k的边数。(算每条边对总值的贡献)。最后再/=2。因为重复考虑了。

代码(有自己调试的过程emmm(连调试方法都比较农民,从来没用过编译器自带的调试功能emmm(队友再用,我没了解))):

#include <bits/stdc++.h>#define ll long long
#define pi acos(-1)
#define pb push_back
#define mst(a, i) memset(a, i, sizeof(a))
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define dbg(x) cout << #x << "===" << x << endl
using namespace std;
template <class T> void read(T &x) {T res = 0, f = 1;char c = getchar();while (!isdigit(c)) {if (c == '-') f = -1;c = getchar();}while (isdigit(c)) {res = (res << 3) + (res << 1) + c - '0';c = getchar();}x = res * f;
}
void print(ll x) {if (x < 0) {putchar('-');x = -x;}if (x > 9) print(x / 10);putchar(x % 10 + '0');
}
const ll maxn = 1e6 + 10;
const ll mod = 1e9 + 7;ll n, x[maxn],y[maxn];
set<pll> st,st1[maxn];
map<pll,ll> mp;
ll cnt=0;
vector<pll> jc;
ll gcd(ll a,ll b){return (b==0)?a:gcd(b,a%b);}
// ll qpow(ll a,ll p,ll mod){ll
// ans=1;a=a%mod;while(p){if(p&1)ans=(ans*a)%mod;p>>=1;a=(a*a)%mod;}return ans;}
int main() {ll _s = 1;// read(_s);for (ll _ = 1; _ <= _s; _++) {read(n);for(ll i=1;i<=n;i++) read(x[i]),read(y[i]);//,dbg(gcd(x[i],y[i]));ll tx,ty,t,cx,cy,ct,c;ll ans=0;jc.pb({1e10,1e10});for(ll i=1;i<=n;i++){st.clear();for(ll j=1;j<=n;j++){if(i==j) continue;//dbg(i),dbg(j);ty=y[j]-y[i];tx=x[j]-x[i];t=gcd(tx,ty);tx/=t,ty/=t;if(tx<0) tx*=-1,ty*=-1;st.insert({tx,ty});//?k=ty/txif(j<=i) continue;//cout<<tx<<" "<<ty<<endl;if(mp[{tx,ty}]==0) mp[{tx,ty}]=++cnt,jc.pb({tx,ty});c=mp[{tx,ty}];//dbg(c);if(tx==0) st1[c].insert({1,x[i]});//,cout<<"cx,cy="<<1<<" "<<x[i]<<endl;else{cx=tx;cy=tx*y[i]-ty*x[i];ct=gcd(cy,cx);//dbg(cx),dbg(cy),dbg(ct);cx/=ct,cy/=ct;if(cx<0) cx*=-1,cy*=-1;st1[c].insert({cx,cy});//cout<<"cx,cy="<<cx<<" "<<cy<<endl;}}//ans+=st.size();}/*for(ll i=1;i<=cnt;i++){dbg(i);cout<<jc[i].fi<<" "<<jc[i].se<<endl;dbg(st1[i].size());for(auto j:st1[i]){cout<<j.fi<<" "<<j.se<<endl;}}*///if(ans==n) ans=0;st.clear();ll sum=0;for(ll i=1;i<=cnt;i++) sum+=st1[i].size();for(ll i=1;i<=cnt;i++) ans+=(sum-st1[i].size())*st1[i].size(),st1[i].clear();ans/=2;cout<<ans<<endl;}return 0;
}
/*
input:::output:::*/

 

  相关解决方案