列表

详情

NC24626. [USACO 2011 Mar S]Bovine Bridge Battle

描述

Each of Farmer John's N (4 <= N <= 1,000) cows is patiently waiting in the main pasture with cow i at point with integer coordinates (X_i, Y_i) (-1,000,000,000 <= X_i <= 1,000,000,000; -1,000,000,000 <= Y_i <= 1,000,000,000).
The cows wish to form into groups of four in order to play Bridge, their new favorite card game. Each group must satisfy an important constraint: four cows are allowed to team up if and only if there exists some point X somewhere in the plane (and not coincident with any of the four points of the potential group of four) such that rotating any of the group's cows 180 degrees about that point X gives the position of some other cow in the group.
Please help the cows determine the number of sets of four cows that can form a Bridge group.
The supplied locations of the cows given are all distinct, although they are supplied in no particular order. Furthermore, the answer will fit into a signed 32-bit integer.

输入描述

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains two space-separated integers: X_i and Y_i

输出描述

* Line 1: A single integer that is the number of sets of 4 cows that form valid groups for bridge.

示例1

输入: 

8 
-3 0 
-2 0 
-1 1 
0 3 
2 0 
-3 1 
3 0 
-2 2

输出: 

3

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 834ms, 内存消耗: 31676K, 提交时间: 2020-01-11 17:33:16 

#pragma GCC target("popcnt")
#pragma GCC optimize("Ofast,inline")
#pragma comment(linker,"/STACK:1024000000,1024000000")
#undef __STRICT_ANSI__
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cctype>
#include <sstream>
#include <cfloat>
#include <complex>
#include <climits>
#include <new>
#include <memory>
#include <cerrno>
#include <cassert>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <bitset>
#include <utility>
#include <iterator>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <cstddef>
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <streambuf>
#include <cfenv>
#include <tuple>
#include <cstdint>
#include <random>
#include <regex>
#define lc c[0]
#define rc c[1]
#define fir first
#define sec second
#define lson x<<1
#define rson x<<1|1
#define PB push_back
#define PF push_front
#define MP make_pair
#define MT make_tuple
#define EB emplace_back
#define EF emplace_front
#define Lson l,m,lson
#define Rson m+1,r,rson
#define LB lower_bound
#define UB upper_bound
#define npos string::npos
#define FF fflush(stdout)
#define PQ priority_queue
#define rint register int
#define LSON L,m,l,m,lson
#define RSON m+1,R,m+1,r,rson
#define sqr(X) ((X)*(X))
#define cbr(X) ((X)*(X)*(X))
#define LBT(X) ((X)&(-(X)))
#define SZ(X) (int)(X).size()
#define ALL(X) (X).begin(),(X).end()
#define INS(X) inserter((X),(X).begin())
#define POS(X,Y,Z) LB((X),(Y),(Z))-(X)+1
#define CPY(X,Y) memcpy((X),(Y),sizeof((Y)))
#define MEM(X,Y) memset((X),(Y),sizeof((X)))
#define SC(X) while(scanf("%s",(X)),!strlen((X)))
#define NUM(X,Y,L,R) UB((X),(Y),(R))-LB((X),(Y),(L))
#define SU(X,Y,Z) sort((X),(Y)),(Z)=unique((X),(Y))-(X)
#define FIO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF 0x3f3f3f3f
#define NNF 0xc0c0c0c0
#define INF64 0x3f3f3f3f3f3f3f3fLL
#define NNF64 0xc0c0c0c0c0c0c0c0LL
#define PH 0.75
#define P 131
using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned int UI;
typedef unsigned long long ULL;
typedef pair<LL,LL> PLL;
typedef pair<int,LL> PIL;
typedef pair<LL,int> PLI;
typedef pair<int,int> PII;
typedef pair<char,int> PCI;
typedef pair<int,char> PIC;
typedef pair<int,string> PIS;
typedef pair<string,int> PSI;
typedef pair<double,int> PDI;
typedef pair<int,double> PID;
typedef pair<double,double> PDD;
typedef pair<string,string> PSS;
typedef tuple<LL,LL,LL> PLLL;
typedef tuple<LL,LL,int> PLLI;
typedef tuple<int,LL,LL> PILL;
typedef tuple<LL,int,int> PLII;
typedef tuple<int,int,LL> PIIL;
typedef tuple<int,int,int> PIII;
typedef tuple<LL,LL,LL,LL> PLLLL;
typedef tuple<int,int,int,int> PIIII;
typedef tuple<double,double,int> PDDI;
typedef tuple<double,double,double> PDDD;
typedef tuple<double,double,double,int> PDDDI;
typedef set<LL> SL;
typedef set<int> SI;
typedef set<PII> SPII;
typedef set<PIL> SPIL;
typedef set<PLI> SPLI;
typedef set<PLL> SPLL;
typedef set<PIII> SPIII;
typedef set<PLLL> SPLLL;
typedef set<string> SS;
typedef queue<LL> QL;
typedef queue<int> QI;
typedef queue<PII> QPII;
typedef queue<PIL> QPIL;
typedef queue<PLI> QPLI;
typedef queue<PLL> QPLL;
typedef deque<LL> DL;
typedef deque<int> DI;
typedef deque<PII> DPII;
typedef deque<PIL> DPIL;
typedef deque<PLI> DPLI;
typedef deque<PLL> DPLL;
typedef complex<LL> CL;
typedef complex<int> CI;
typedef complex<double> CD;
typedef vector<LL> VL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<PII> VPII;
typedef vector<PIL> VPIL;
typedef vector<PLI> VPLI;
typedef vector<PLL> VPLL;
typedef vector<PIC> VPIC;
typedef vector<PCI> VPCI;
typedef vector<PID> VPID;
typedef vector<PDI> VPDI;
typedef vector<PIS> VPIS;
typedef vector<PSI> VPSI;
typedef vector<string> VS;
typedef vector<PIII> VPIII;
typedef vector<PIIL> VPIIL;
typedef vector<PILL> VPILL;
typedef vector<PLLL> VPLLL;
typedef vector<PLII> VPLII;
typedef vector<PLLI> VPLLI;
typedef vector<PIIII> VPIIII;
typedef vector<PLLLL> VPLLLL;
typedef map<LL,LL> MLL;
typedef map<int,LL> MIL;
typedef map<LL,int> MLI;
typedef map<int,int> MII;
typedef map<PII,int> MPIII;
typedef map<PLL,int> MPLLI;
typedef map<string,int> MSI;
typedef map<VI,int> MVII;
template<typename T> T gcd(T x,T y) {return y?gcd(y,x%y):x;}
template<typename T> T lcm(T x,T y) {return x/gcd(x,y)*y;}
template<typename T> void adn(T &x,T y,T z) {x=min(z,x+y);}
template<typename T> void adm(T &x,T y,T z) {x=x+y;if(x>=z)x=x-z;}
template<typename T> void adj(T &x,T y) {if(x>=y||x<=-y)x=x%y;if(x<0)x=x+y;}
template<typename T> T qpow(T x,LL y,T z) {for(;y;y>>=1,x=x*x)if(y&1)z=z*x;return z;}
template<typename T> T mpow(LL w,T x,LL y,T z) {for(;y;y>>=1,x=x*x,x=x%w)if(y&1)z=z*x,z=z%w;return z;}
template<typename T> T exgcd(T a,T b,T &x,T &y) {T t=a;b?(t=exgcd(b,a%b,y,x),y=y-(a/b)*x):(x=1,y=0);return t;}
const double EPS = 1e-7;
const LL MOD = 1000000007LL;
const int M = 5000005;
const int N = 1005;
int n,ans;
PII a[N];
MPIII mp;

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d %d",&a[i].fir,&a[i].sec);
    for (int i=1;i<=n;i++)
    for (int j=i+1;j<=n;j++) mp[MP(a[i].fir+a[j].fir,a[i].sec+a[j].sec)]++;
    for (auto &i : mp) ans+=i.sec*(i.sec-1)/2LL;
    printf("%d\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 662ms, 内存消耗: 31720K, 提交时间: 2020-01-11 08:01:26 

#include<bits/stdc++.h>
#define mo 1000000007
#define pi 3.1415926535898
#define eps 1e-9 
using namespace std;
long long read(){
    long long xx=0,flagg=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')
        ch=getchar();
    if(ch=='-'){
        flagg=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        xx=xx*10+ch-'0';
        ch=getchar();
    }
    return xx*flagg;
}
void pus(long long xx,long long flagg){
    if(xx<0){
        putchar('-');
        xx=-xx;
    }
    if(xx>=10)
        pus(xx/10,0);
    putchar(xx%10+'0');
    if(flagg==1)
        putchar(' ');
    if(flagg==2)
        putchar('\n');
    return;
}
long long n,i,j,x[1005],y[1005],ans;
map<pair<long long,long long>,long long> mp;
int main(){
	n=read();
	for(i=1;i<=n;i++){
		x[i]=read();
		y[i]=read();
	}
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
			mp[make_pair(x[i]+x[j],y[i]+y[j])]++;
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
			ans+=mp[make_pair(x[i]+x[j],y[i]+y[j])]-1;
	pus(ans/2,2);
    return 0;
}

上一题

© 2024 nowcoder.com